zbMATH — the first resource for mathematics

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.
MSC:
 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs 05C07 Vertex degrees
Full Text:
References:
 [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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.