×

On non-Hamiltonian graphs for which every vertex-deleted subgraph is traceable. (English) Zbl 1370.05115

Summary: We call a graph \(G\) a platypus if \(G\) is non-Hamiltonian, and for any vertex \(v\) in \(G\), the graph \(G-v\) is traceable. Every hypo-Hamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypo-Hamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of G. Wiener [ibid. 84, No. 4, 443–459 (2017; Zbl 1359.05072)]. We also prove that there exists a \(k\)-connected platypus for every \(k\geq 2\).

MSC:

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 1359.05072
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] M.Araya and G.Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron J Combin18 (2011), #P85. · Zbl 1217.05065
[2] G.Brinkmann and N.VanCleemput, Personal communication.
[3] O. D.Byer and D. L.Smeltzer, Edge bounds in nonhamiltonian k‐connected graphs, Discrete Math307 (2007), 1572-1579. · Zbl 1123.05051
[4] V.Chvátal, Flip‐flops in hypohamiltonian graphs, Canad Math Bull16 (1973), 33-41. · Zbl 0253.05142
[5] V.Chvátal, New directions in hamiltonian graph theory, In: New Directions in the Theory of Graphs (F.Harary (ed.), Ed.), Academic Press, New York, 1973, pp. 65-95. · Zbl 0271.05120
[6] V.Chvátal, Tough graphs and hamiltonian circuits, Discrete Math5 (1973), 215-228. · Zbl 0256.05122
[7] H. S. M.Coxeter, Self‐dual configurations and regular graphs, Bull Am Math Soc56 (1950), 413-455. · Zbl 0040.22803
[8] S.Fiorini, Hypohamiltonian snarks, In: Graphs and other combinatorial topics (M.Fiedler (ed.), Ed.), Proc. of 3rd Czechoslovak Symposium on Graph Theory, Prague, August 24-27, 1982, Teubner‐Texte zur Math., Bd. 59, Teubner, Leipzig, 1983, pp. 70-75. · Zbl 0535.05045
[9] T.Gallai, Problem 4, In: Theory of Graphs (P.Erdős (ed.) and G.Katona (ed.), Eds.), Proc. Tihany 1966, Academic Press, New York, 1968, p. 362. · Zbl 0155.00201
[10] L.Gargano, M.Hammar, P.Hell, L.Stacho, and U.Vaccaro, Spanning spiders and light‐splitting switches, Discrete Math285 (2004), 83-95. · Zbl 1044.05048
[11] J.Goedgebeur and C. T.Zamfirescu, New results on hypohamiltonian and almost hypohamiltonian graphs. Submitted. arXiv:1606.06577 [math.CO]. To appear in Ars Math Contemp.
[12] J.Goedgebeur and C. T.Zamfirescu, On Hypohamiltonian Snarks and a Theorem of Fiorini. Submitted. arXiv:1608.07164 [math.CO]. To appear in Ars Math Contemp.
[13] E. J.Grinberg, Plane homogeneous graphs of degree three without Hamiltonian circuits, Latvian Math Yearbook4 (1968), 51-58 (Russian). · Zbl 0185.27901
[14] S.Gutt, Infinite families of hypohamiltonian graphs, Acad Roy Belg Bull Cl Sci V Sér63 (1977), 432-440. · Zbl 0367.05047
[15] R.Halin, Zur Theorie der n‐fach zusammenhängenden Graphen, Abh Math Sem Hamburg33 (1969), 133-164. · Zbl 0172.25802
[16] J. C.Herz, Sur la cyclabilité des graphes, Computers in Math. Research, North‐Holland Publ., Amsterdam 1968, pp. 97-107. · Zbl 0179.29104
[17] D. A.Holton, B. D.McKay, M. D.Plummer, and C.Thomassen, Cycles through specified vertices in 3‐connected graphs, Combinatorica1 (1981), 409-418.
[18] D. A.Holton and J.Sheehan, The Petersen Graph, Chapter 7: Hypohamiltonian graphs, Cambridge University Press, New York, 1993. · Zbl 0781.05001
[19] R.Isaacs, Infinite families of non‐trivial trivalent graphs which are not Tait‐colorable, Am Math Monthly82 (1975), 221-239. · Zbl 0311.05109
[20] S.Jendrol’ and Z.Skupień, Exact numbers of longest cycles with empty intersection, Eur J Combin18 (1997), 575-578. · Zbl 0879.05040
[21] M.Jooyandeh, B. D.McKay, P. R. J.Östergård, V. H.Pettersson, and C. T.Zamfirescu, Planar hypohamiltonian graphs on 40 vertices, J Graph Theory84 (2017), 121-133. · Zbl 1356.05029
[22] E.Máčajová and M.Škoviera, Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6, Electron J Combin14 (2007), # R18. · Zbl 1110.05057
[23] E.Máčajová and M.Škoviera, Infinitely many hypohamiltonian cubic graphs of girth 7, Graphs Combin27 (2011), 231-241. · Zbl 1235.05085
[24] B. D.McKay, Hypohamiltonian planar cubic graphs with girth 5, J Graph Theory DOI: 10.1002/jgt.22043. arXiv:1507.07197 [math.CO]. · Zbl 1365.05064
[25] G. H. J.Meredith, Regular n‐valent n‐connected nonhamiltonian non‐n‐edge‐colorable graphs, J Combin Theory Ser B14 (1973), 55-60. · Zbl 0237.05106
[26] T.Nishizeki, A 1‐tough nonhamiltonian maximal planar graph, Discrete Math30 (1980), 305-307. · Zbl 0442.05046
[27] J.Petersen, Die Theorie der regulären Graphs, Acta Math15 (1891), 193-220.
[28] G. N.Robertson, Graphs minimal under girth, valency and connectivity constraints, Ph. D. thesis, University of Waterloo, Waterloo, Ontario, Canada, 1969.
[29] A.Shabbir, C. T.Zamfirescu, and T. I.Zamfirescu, Intersecting longest paths and longest cycles: A survey, Electron J Graph Theory Appl1 (2013), 56-76. · Zbl 1306.05121
[30] P. G.Tait, Remarks on the colourings of maps, Proc R Soc Edinburgh10 (1880), 729.
[31] C.Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math9 (1974), 91-96. · Zbl 0278.05110
[32] C.Thomassen, On hypohamiltonian graphs, Discrete Math10 (1974), 383-390. · Zbl 0286.05122
[33] C.Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math14 (1976), 377-389. · Zbl 0322.05130
[34] C.Thomassen, Hypohamiltonian graphs and digraphs, Theory and Applications of Graphs, Lecture Notes in Mathematics 642, Springer, Berlin, 1978, pp. 557-571. · Zbl 0371.05015
[35] C.Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J Combin Theory Ser B30 (1981), 36-44. · Zbl 0388.05033
[36] W. T.Tutte, A theorem on planar graphs, Trans Am Math Soc82 (1956), 99-116. · Zbl 0070.18403
[37] N.VanCleemput, Personal communication.
[38] H.Walther, Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen, J Combin Theory6 (1969), 1-6. · Zbl 0184.27504
[39] M. E.Watkins, A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs, J Combin Theory6 (1969), 152-164. · Zbl 0175.50303
[40] G.Wiener, Leaf‐critical and leaf‐stable graphs, J Graph Theory DOI: 10.1002/jgt.22034. · Zbl 1359.05072
[41] G.Wiener and M.Araya, On planar hypohamiltonian graphs, J Graph Theory67 (2011), 55-68. · Zbl 1223.05168
[42] C. T.Zamfirescu, Hypohamiltonian graphs and their crossing number, Electron J Combin19 (2012), #P12. · Zbl 1266.05079
[43] C. T.Zamfirescu, On hypohamiltonian and almost hypohamiltonian graphs, J Graph Theory79 (2015), 63-81. · Zbl 1312.05076
[44] C. T.Zamfirescu and T. I.Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J Graph Theory55 (2007), 338-342. · Zbl 1120.05054
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.