Simple Proofs of Two Dirac-type Theorems Involving Connectivity
Keywords:
Minimum degree, Connectivity, CircumferenceAbstract
In 1981, the third author proved that each 2-connected graph G with δ ≥ (n+k)/3 is hamiltonian and each 3-connected graph contains a cycle of length at least min {n, 3δ-k}, where n denotes the order, δ - the minimum degree and k- the connectivity of G. Short proofs of these two results were given by Häggkvist and Yamashita, respectively, occupying more than three pages for actual proofs altogether. Here we give much simpler and shorter proofs actually occupying the two-thirds of a page.
References
J.A . Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.
G.A. Dirac, “Some theorems on abstract graphs", Proc. London, Math. Soc., vol. 2, pp. 69-81, 1952.
R. Häggkvist and G.G. Nicoghossian, “A remark on hamiltonian cycles", Journal Combin. Theory, Ser. B 30, pp. 118-120, 1981.
C. St. J. A . Nash-Williams, Studies in Pure Mathematics, (Edge-disjoint hamiltonian cycles in graphs with vertices of large valency, pp. 157-183), in: L. Mirsky (Ed) , Academic Press, San Diego, London, 1971.
Zh. G. Nikoghosyan, “On maximal cycle of a graph" ,DAN Arm.SSR, (in Russian), vol. LXXII, no. 2, pp. 82-87, 1981.
H.-J. Voss and C. Zuluaga, “Maximale gerade und ungerade Kreise in Graphen I" , Wiss. Z. Tech. Hochschule Ilmenau, vol. 23, pp. 57-70, 1 977. ( Math. Soc., vol. 2 pp. 69-81, 1952.)
T. Yamashita, “A degree sum condition for longest cycles in 3-connected graphs", Journal of Graph Theory, vol. 54, no. 4, pp. 277-283, 2007.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
