DMGT

Discussiones Mathematicae Graph Theory 19(1) (1999) 13-29
DOI: https://doi.org/10.7151/dmgt.1082

EXTREMAL PROBLEMS FOR FORBIDDEN PAIRS THAT IMPLY HAMILTONICITY

Ralph Faudree

Department of Mathematical Sciences
University of Memphis, Memphis, TN 38152

András Gyárfás

Computer and Automation Institute
Hungarian Academy of Sciences
Budapest, Hungary

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.

References

[1]	P. Bedrossian, Forbidden subgraph and minimum degree conditions for hamiltonicity, Ph.D Thesis, Memphis State University, 1991.
[2]	J.A. Bondy and U.S.R. Murty, Graph Theory With Applications (Macmillan, London and Elsevier, New York, 1976).
[3]	G. Chartrand and L. Lesniak, Graphs and Digraphs (2nd ed., Wadsworth and Brooks/Cole, Belmont, 1986).
[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]	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.
[6]	R.J. Faudree, Forbidden Subgraphs and Hamiltonian Properties - A Survey, Congressus Numerantium 116 (1996) 33-52.
[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.
[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.
[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.
[10]	O. Ore, Note on Hamiltonian Circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.

Received 16 February 1998
Revised 8 December 1998