Extremal problems for forbidden pairs that imply hamiltonicity

Ralph Faudree; András Gyárfás

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 1, page 13-29
  • ISSN: 2083-5892

Abstract

top
Let C denote the claw K 1 , 3 , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and Z i the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does not contain an induced copy of C or of Y) will be determined for Y a connected subgraph of either P₆, N, W, or Z₃. It should be noted that the pairs of graphs CY are precisely those forbidden pairs that imply that any 2-connected graph of order at least 10 is hamiltonian. These extremal numbers give one measure of the relative strengths of the forbidden subgraph conditions that imply a graph is hamiltonian.

How to cite

top

Ralph Faudree, and András Gyárfás. "Extremal problems for forbidden pairs that imply hamiltonicity." Discussiones Mathematicae Graph Theory 19.1 (1999): 13-29. <http://eudml.org/doc/270578>.

@article{RalphFaudree1999,
abstract = {Let C denote the claw $K_\{1,3\}$, N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_i$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does not contain an induced copy of C or of Y) will be determined for Y a connected subgraph of either P₆, N, W, or Z₃. It should be noted that the pairs of graphs CY are precisely those forbidden pairs that imply that any 2-connected graph of order at least 10 is hamiltonian. These extremal numbers give one measure of the relative strengths of the forbidden subgraph conditions that imply a graph is hamiltonian.},
author = {Ralph Faudree, András Gyárfás},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamiltonian; extremal numbers; forbidden subgraph; dense graphs; sparse graphs},
language = {eng},
number = {1},
pages = {13-29},
title = {Extremal problems for forbidden pairs that imply hamiltonicity},
url = {http://eudml.org/doc/270578},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Ralph Faudree
AU - András Gyárfás
TI - Extremal problems for forbidden pairs that imply hamiltonicity
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 1
SP - 13
EP - 29
AB - Let C denote the claw $K_{1,3}$, N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and $Z_i$ the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does not contain an induced copy of C or of Y) will be determined for Y a connected subgraph of either P₆, N, W, or Z₃. It should be noted that the pairs of graphs CY are precisely those forbidden pairs that imply that any 2-connected graph of order at least 10 is hamiltonian. These extremal numbers give one measure of the relative strengths of the forbidden subgraph conditions that imply a graph is hamiltonian.
LA - eng
KW - hamiltonian; extremal numbers; forbidden subgraph; dense graphs; sparse graphs
UR - http://eudml.org/doc/270578
ER -

References

top
  1. [1] P. Bedrossian, Forbidden subgraph and minimum degree conditions for hamiltonicity, Ph.D Thesis, Memphis State University, 1991. 
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory With Applications (Macmillan, London and Elsevier, New York, 1976). 
  3. [3] G. Chartrand and L. Lesniak, Graphs and Digraphs (2nd ed., Wadsworth and Brooks/Cole, Belmont, 1986). Zbl0666.05001
  4. [4] G. Dirac, Some Theorems on Abstract Graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. 
  5. [5] P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, On Cycle Complete Graph Ramsey Numbers, J. Graph Theory 2 (1978) 53-64, doi: 10.1002/jgt.3190020107. Zbl0383.05027
  6. [6] R.J. Faudree, Forbidden Subgraphs and Hamiltonian Properties - A Survey, Congressus Numerantium 116 (1996) 33-52. Zbl0895.05037
  7. [7] R.J. Faudree, E. Flandrin and Z. Ryjácek, Claw-free Graphs - A Survey, Discrete Math. 164 (1997) 87-147, doi: 10.1016/S0012-365X(96)00045-3. Zbl0879.05043
  8. [8] R.J. Faudree and R.J. Gould, Characterizing Forbidden Pairs for Hamiltonian Properties, Discrete Math. 173 (1977) 45-60, doi: 10.1016/S0012-365X(96)00147-1. Zbl0879.05050
  9. [9] J.K. Kim, The Ramsey number R(3,t) has order of magnitude t²/logt, Random Structures Algorithms 7 (1995) 173-207, doi: 10.1002/rsa.3240070302. Zbl0832.05084
  10. [10] O. Ore, Note on Hamiltonian Circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928. 

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.