Chvátal-Erdös type theorems

Jill R. Faudree; Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Colton Magnant

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 2, page 245-256
  • ISSN: 2083-5892

Abstract

top
The Chvátal-Erdös 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 condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.

How to cite

top

Jill R. Faudree, et al. "Chvátal-Erdös type theorems." Discussiones Mathematicae Graph Theory 30.2 (2010): 245-256. <http://eudml.org/doc/270915>.

@article{JillR2010,
abstract = {The Chvátal-Erdös 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 condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.},
author = {Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamiltonian; Hamiltonian-connected; Chvátal-Erdös condition; independence number; Chvátal-Erdős condition},
language = {eng},
number = {2},
pages = {245-256},
title = {Chvátal-Erdös type theorems},
url = {http://eudml.org/doc/270915},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Jill R. Faudree
AU - Ralph J. Faudree
AU - Ronald J. Gould
AU - Michael S. Jacobson
AU - Colton Magnant
TI - Chvátal-Erdös type theorems
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 2
SP - 245
EP - 256
AB - The Chvátal-Erdös 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 condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1), and δ(G) ≥ α(G)+k-2, then G is hamiltonian. It is shown that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ 4k²+1, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected. This result supports the conjecture that if G is a graph of order n and k ≥ 3 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-2k)/k, and δ(G) ≥ α(G)+k-2, then G is hamiltonian-connected, and the conjecture is verified for k = 3 and 4.
LA - eng
KW - Hamiltonian; Hamiltonian-connected; Chvátal-Erdös condition; independence number; Chvátal-Erdős condition
UR - http://eudml.org/doc/270915
ER -

References

top
  1. [1] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, London, 1996). Zbl0890.05001
  2. [2] V. Chvátal and P. Erdös, A note on Hamiltonian circuits, Discrete Math 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9. Zbl0233.05123
  3. [3] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
  4. [4] H. Enomoto, Long paths and large cycles in finite graphs, J. Graph Theory 8 (1984) 287-301, doi: 10.1002/jgt.3190080209. Zbl0544.05044
  5. [5] P. Fraisse, D λ -cycles and their applications for hamiltonian cycles, Thése de Doctorat d’état (Université de Paris-Sud, 1986). 
  6. [6] K. Ota, Cycles through prescribed vertices with large degree sum, Discrete Math. 145 (1995) 201-210, doi: 10.1016/0012-365X(94)00036-I. Zbl0838.05071

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.