A note on two circumference generalizations of Chvátal’s Hamiltonicity condition. (English) Zbl 1006.05036

Generalizing the well-known Chvátal’s Hamiltonicity condition B. Bollobás in his classical book on extremal graph theory asked: Let \(G\) be a \(2\)-connected graph of order \(n\) with vertex degrees \(d_1 \leq d_2 \leq \dots \leq d_n\). Suppose \(3 \leq c \leq n\) and \(d_i \leq i < c/2\) implies \(d_{n-i} \geq c-i\). Does it follow that for the circumference \(c(G)\) of \(G\) (the length of its longest cycle) \(c(G) \geq c\) holds? For \(c=3\) and \(c=4\) this follows directly from the \(2\)-connectivity of \(G\), however Häggkvist found counterexamples for any \(c \geq 7\). In the paper the author proves that for \(c=5\) the answer is affirmative while for \(c=6\) counterexamples are presented. An interesting generalization of Chvátal’s condition for any \(c\) is formulated and proved.


05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C07 Vertex degrees
Full Text: EuDML


[1] BEDROSSIAN P., CHEN G., SCHELP R. H.: A generalization of Fan’s condition for hamiltonicity, pancyclicity, and hamiltonian connectedness. Discrete Math. 115 (1993), 39-50. · Zbl 0773.05075
[2] BOLLOBÁS B.: Extremal Graph Theory. Acad. Press, London-New York-San Francisco, 1978. · Zbl 1099.05044
[3] BOLLOBÁS B., BRIGHTWELL G.: Cycles through specified vertices. Combinatorica 13 (1993), 147 -155. · Zbl 0780.05033
[4] BONDY J. A.: Large cycles in graphs. Discrete Math. 1 (1971), 121-132. · Zbl 0224.05120
[5] BONDY J. A., LOVÁSZ L.: Cycles through specified vertices of a graph. Combinatorica 1 (1981). 117-140. · Zbl 0492.05049
[6] HÄGGKVIST R.: · Zbl 1218.05129
[7] CHVÁTAL V.: On hamilton’s ideals. J. Combin. Theory Ser. B 12 (1972), 163-168. · Zbl 0213.50803
[8] SHI R.: 2-Neighborhoods and hamiltonian conditions. J. Graph Theory 16 (1992), 267-271. · Zbl 0761.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.