Abstract
Methods for constructing hypohamiltonian graphs and oriented graphs are described. It is shown that every planar hypohamiltonian graph contains a vertex of degree 3 and that for each n ≥ 6 there exists a planar, hypohamiltonian digraph with n vertices. Finally it is proved that every graph with n vertices contains a set A of at most 1/3n vertices such that every longest cycle of the graph intersects A.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
J.A. Bondy, Variations on the hamiltonian theme Can. Math. Bull. 15 (1972) 57–62.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. MacMillan, London 1975.
V. Chvátal, Flip-flops in hypohamiltonian graphs. Can. Math. Bull. 16 (1973) 33–41.
V. Chvátal, New directions in hamiltonian graph theory, in: F. Harary, Ed., New Directions in Graph Theory. Academic Press, New York (1973).
J.B. Collier and E.F. Schmeichel, New flip-flop constructions for hypohamiltonian graphs, to appear.
J.B. Collier and E.F. Schmeichel, Systematic searches for hypohamiltonian graphs, to appear.
J. Doyen and V. Van Diest, New families of hypohamiltonian graphs. Discrete Math. 13 (1975) 225–236.
B. Grünbaum, Vertices missed by longest paths or circuits. J. Combinatorial Theory 17 (1974) 31–38.
F. Harary and C. Thomassen, Anticritical graphs, Math.Proc.Camb.Phil.Soc. 79 (1976) 11–18.
F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969).
J.C. Herz, J.J. Duby and F. Vigué, Rechereche systématique des graphes hypohamiltonien, in: P. Rosenstiehl, Ed., Theorie des Graphes. Dunod, Paris (1967) 153–160.
J.C. Herz, T. Gaudin and P. Rossi, Solution du problème No. 29. Rev. Franc. Rech. Opérat. 8 (1964) 214–218.
W.F. Lindgren, An infinite class of hypohamiltonian graphs. Am.Math.Monthly 74 (1967) 1087–1089.
C. Thomassen, Hypohamiltonian and Hypotraceable graphs. Discrete Math. 9 (1974) 91–96.
C. Thomassen, On hypohamiltonian graphs. Discrete Math. 10 (1974) 383–390.
C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs. Discrete Math. 14 (1976) 377–389.
W.T. Tutte, A theorem on planar graphs. Trans. Am. Math. Soc. 82 (1956) 99–116.
W.T. Tutte, A non-Hamiltonian graph. Can. Math. Bull. 3 (1960) 1–5.
T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combinatorial Theory, Ser. B. 13 (1972) 116–121.
T. Zamfirescu, On longest paths and circuits in graphs. Math. Scand., to appear.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1978 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Thomassen, C. (1978). Hypohamiltonian graphs and digraphs. In: Alavi, Y., Lick, D.R. (eds) Theory and Applications of Graphs. Lecture Notes in Mathematics, vol 642. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0070410
Download citation
DOI: https://doi.org/10.1007/BFb0070410
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08666-6
Online ISBN: 978-3-540-35912-8
eBook Packages: Springer Book Archive