一个Chvátal-Erd（？）s型定理
|
摘要
Chvatal-Erdos定理指出如果G是阶数n≥3的图，且κ(G)≥α(G)，那么G是Hamilton图；如果κ(G)>α(G)，那么G是Hamilton连通图。我们在连通度足够大的情况下用限制更弱的最小度和独立数条件之间的关系取代原有的连通度和独立数条件之间的关系得到了一些新的结果。我们将证明如果G是阶数为n的图，n充分大，k是大于等于3的正整数，使得κ(G)≥2k~2+4k+1，δ(G)>(n+k~2-2k)／k，并且δ(G)>α(G)+k-2，那么G是Hamilton连通图。
The Chvatal-Erdos theorems imply that if G is a graph of order n≥3 withκ(G)≥α(G), then G is hamiltonian, and ifκ(G) >α(G),then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number conditions in the presence of sufficient connectivity.
We show that if G is a graph of order n and k≥3 is a positive integer such thatκ(G)≥2k~2+4k + 1 ,δ(G)>(n + k~2-2k)/k , andδ(G)>α(G) + k-2 ,then G is hamiltonian-connected.
The Chvatal-Erdos theorems imply that if G is a graph of order n≥3 withκ(G)≥α(G), then G is hamiltonian, and ifκ(G) >α(G),then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number conditions in the presence of sufficient connectivity.
We show that if G is a graph of order n and k≥3 is a positive integer such thatκ(G)≥2k~2+4k + 1 ,δ(G)>(n + k~2-2k)/k , andδ(G)>α(G) + k-2 ,then G is hamiltonian-connected.
引文
[1] G.Chartrand and L.Lesniak, Graph and Digraphs, Chapman and Hall, London,(1996).
[2] V.Chvatal and P.Erdos, A note on hamiltonian circuits, Discrete Math.2, (1972).111-113.
[3] GA.Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2(1952),69-81.
[4] H.Enomoto, Long paths and large cycles in finite graphs, Research Report,Department of Information Science, University of Tokyo( 1980).
[5] P.Fraisse, D_λ -cycles and their applications for Hamiltonian cycles, These de Doctoratdetat, Universite de Paris-Sud, (1986)
[6] K.Ota, Cycles through prescribed vertices with large degree sum, Discrete Math.145(1995),201-210.
[7] Jill R.Faudree, Ralph J.Faudree and Colton Magnant, Chvatal-Erdos Type Theorems,preprint.
[8] J.A.Bondy and B.Jackson, Long paths between specified vertices of a block,Ann.DiscreteMath.27(1985),195-200.
[9] Zhiquan Hu ,Feng Tian and Bing Wei,Long Cycles through a Linear Forest, Journalof Combinatorial Theory,Series B 82,67-80(2001).
[10] J.A.Bondy, Integrity in graph theory, in"The theory and Applications of Graph"(G.Chartrand,Y.Alavi,D.L.Goldsmith,L.Lesniak-Foster,and D.R. lick, Eds.),pp. 117-125,wiley,New York, 1981.
[11] J.A.Bondy and U.S.R.Murty,"Graph Theory with Applications,"Macmillan, London/Elsevier, New York, 1976.
[2] V.Chvatal and P.Erdos, A note on hamiltonian circuits, Discrete Math.2, (1972).111-113.
[3] GA.Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2(1952),69-81.
[4] H.Enomoto, Long paths and large cycles in finite graphs, Research Report,Department of Information Science, University of Tokyo( 1980).
[5] P.Fraisse, D_λ -cycles and their applications for Hamiltonian cycles, These de Doctoratdetat, Universite de Paris-Sud, (1986)
[6] K.Ota, Cycles through prescribed vertices with large degree sum, Discrete Math.145(1995),201-210.
[7] Jill R.Faudree, Ralph J.Faudree and Colton Magnant, Chvatal-Erdos Type Theorems,preprint.
[8] J.A.Bondy and B.Jackson, Long paths between specified vertices of a block,Ann.DiscreteMath.27(1985),195-200.
[9] Zhiquan Hu ,Feng Tian and Bing Wei,Long Cycles through a Linear Forest, Journalof Combinatorial Theory,Series B 82,67-80(2001).
[10] J.A.Bondy, Integrity in graph theory, in"The theory and Applications of Graph"(G.Chartrand,Y.Alavi,D.L.Goldsmith,L.Lesniak-Foster,and D.R. lick, Eds.),pp. 117-125,wiley,New York, 1981.
[11] J.A.Bondy and U.S.R.Murty,"Graph Theory with Applications,"Macmillan, London/Elsevier, New York, 1976.