DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(1) (1999) 13-29
DOI: 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 K1,3, N the net (a graph obtained from a K3 by attaching a disjoint edge to each vertex of the K3), W the wounded (a graph obtained from a K3 by attaching an edge to one vertex and a disjoint path P3 to a second vertex), and Zi the graph consisting of a K3 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 P6, N, W, or Z3. 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 t2/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