×
Goedgebeur, Jan; Zamfirescu, Carol T.

Improved bounds for hypo-Hamiltonian graphs. (English) Zbl 1380.05034

Ars Math. Contemp. 13, No. 2, 235-257 (2017).
Summary: A graph \(G\) is hypo-Hamiltonian if \(G\) is non-Hamiltonian and \(G-v\) is hamiltonian for every \(v\in V(G)\). In the following, every graph is assumed to be hypo-Hamiltonian. R. E. L. Aldred et al. [J. Comb. Math. Comb. Comput. 23, 143–152 (1997; Zbl 0880.05061)] gave a list of all graphs of order at most 17. In this article, we present an algorithm to generate all graphs of a given order and apply it to prove that there exist exactly 14 graphs of order 18 and 34 graphs of order 19. We also extend their results in the cubic case. Furthermore, we show that (i) the smallest graph of girth 6 has order 25, (ii) the smallest planar graph has order at least 23, (iii) the smallest cubic planar graph has order at least 54, and (iv) the smallest cubic planar graph of girth 5 with non-trivial automorphism group has order 78.

Cited in 10 Documents

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

Hamiltonian; hypo-Hamiltonian; planar; girth; cubic graph; exhaustive generation

Citations:

Zbl 0880.05061

Software:

nauty; Traces; plantri; GenHypohamiltonian; GENREG; snarkhunter
PDFBibTeX XMLCite
\textit{J. Goedgebeur} and \textit{C. T. Zamfirescu}, Ars Math. Contemp. 13, No. 2, 235--257 (2017; Zbl 1380.05034)
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Number of hypohamiltonian graphs on n vertices.
Number of cubic hypohamiltonian graphs on 2n vertices.

References:

[1] R. E. L. Aldred, S. Bau, D. Holton and B. D. McKay, Nonhamiltonian 3-connected cubic planar graphs, SIAM J. Discrete Math. 13 (2000), 25-32, doi:10.1137/ S0895480198348665. · Zbl 0941.05041
[2] R. E. L. Aldred, B. D. McKay and N. C. Wormald, Small hypohamiltonian graphs, J. Combin. Math. Combin. Comput.23 (1997), 143-152. · Zbl 0880.05061
[3] M. Araya and G. Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin.18 (2011), #P85,http://www.combinatorics.org/ ojs/index.php/eljc/article/view/v18i1p85. · Zbl 1217.05065
[4] J. M. Boyer and W. J. Myrvold, On the cutting edge: simplified O(n) planarity by edge addition, J. Graph Algorithms Appl. 8 (2004), 241-273, doi:10.7155/jgaa.00091. · Zbl 1086.05067
[5] G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. M´elot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (2013), 311-314, doi: 10.1016/j.dam.2012.07.018, available athttp://hog.grinvin.org/. · Zbl 1292.05254
[6] G. Brinkmann and J. Goedgebeur, Generation of cubic graphs and snarks with large girth, J. Graph Theory (2017), doi:10.1002/jgt.22125. · Zbl 1370.05198
[7] G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markstr¨om, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013), 468-488, doi:10.1016/j.jctb. 2013.05.001. · Zbl 1301.05119
[8] G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discrete Math. Theor. Comput. Sci.13 (2011), 69-80,https://www.dmtcs.org/ dmtcs-ojs/index.php/dmtcs/article/view/1801.1.html. · Zbl 1283.05256
[9] G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem.58 (2007), 323-357,http://match.pmf.kg.ac.rs/ electronic_versions/Match58/n2/match58n2_323-357.pdf. · Zbl 1164.68025
[10] G. Chartrand, S. F. Kapoor and D. R. Lick, n-hamiltonian graphs, J. Combinatorial Theory9 (1970), 308-312, doi:10.1016/s0021-9800(70)80069-2. · Zbl 0204.57005
[11] V. Chv´atal, Flip-flops in hypohamiltonian graphs, Canad. Math. Bull. 16 (1973), 33- 41, doi:10.4153/cmb-1973-008-9. · Zbl 0253.05142
[12] J. B. Collier and E. F. Schmeichel, New flip-flop constructions for hypohamiltonian graphs, Discrete Math. 18 (1977), 265-271, doi:10.1016/0012-365x(77)90130-3. · Zbl 0367.05046
[13] J. B. Collier and E. F. Schmeichel, Systematic searches for hypohamiltonian graphs, Networks8 (1978), 193-200, doi:10.1002/net.3230080303. · Zbl 0384.05046
[14] R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, Springer, Heidelberg, 4th edition, 2010, doi:10.1007/978-3-642-14279-6. · Zbl 1204.05001
[15] J. Goedgebeur and C. T. Zamfirescu, New results on hypohamiltonian and almost hypohamiltonian graphs,arXiv:1606.06577[math.CO]. · Zbl 1395.05044
[16] J. Goedgebeur and C. T. Zamfirescu, Hypohamiltonian graphs, 2016, homepage of GenHypohamiltonian,http://caagt.ugent.be/hypoham/. · Zbl 1417.05114
[17] B. Gr¨unbaum, Vertices missed by longest paths or circuits, J. Combin. Theory Ser. A 17 (1974), 31-38, doi:10.1016/0097-3165(74)90025-9. · Zbl 0259.05120
[18] W. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann. 243 (1979), 213-216, doi:10.1007/bf01424541. · Zbl 0396.05032
[19] J. C. Herz, J. J. Duby and F. Vigu´e, Recherche syst´ematique des graphes hypohamiltoniens, in: P. Rosentiehl (ed.), Theory of Graphs: International Symposium, Rome, July 1966, Dunod, Paris, 1967 pp. 153-159. · Zbl 0196.56102
[20] D. A. Holton and B. D. McKay, The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory Ser. B 45 (1988), 305-319, doi: 10.1016/0095-8956(88)90075-5. · Zbl 0607.05051
[21] D. A. Holton and J. Sheehan, The Petersen Graph, volume 7 of Australian Mathematical Society Lecture Series, Cambridge University Press, New York, 1993, doi: 10.1017/cbo9780511662058. · Zbl 0781.05001
[22] M. Jooyandeh, B. D. McKay, P. R. J. ¨Osterg˚ard, V. H. Pettersson and C. T. Zamfirescu, Planar hypohamiltonian graphs on 40 vertices, J. Graph Theory 84 (2017), 121-133, doi:10.1002/jgt.22015. · Zbl 1356.05029
[23] F. Kardoˇs, A computer-assisted proof of Barnette’s conjecture: not only fullerene graphs are hamiltonian,arXiv:1409.2440[math.CO].
[24] E. M´aˇcajov´a and M. ˇSkoviera, Infinitely many hypohamiltonian cubic graphs of girth 7, Graphs Combin. 27 (2011), 231-241, doi:10.1007/s00373-010-0968-z. · Zbl 1235.05085
[25] B. D. McKay, Combinatorial Data - Graphs, page with hypohamiltonian graphs, http://users.cecs.anu.edu.au/˜bdm/data/graphs.html.
[26] B. D. McKay, nauty User’s Guide (Version 2.5), technical report TR-CS-90-02, Department of Computer Science, Australian National University,http://cs.anu. edu.au/˜bdm/nauty.
[27] B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), 306- 324, doi:10.1006/jagm.1997.0898. · Zbl 0894.68107
[28] B. D. McKay, Hypohamiltonian planar cubic graphs with girth five, J. Graph Theory (2016), doi:10.1002/jgt.22043.
[29] B. D. McKay, W. Myrvold and J. Nadon, Fast backtracking principles applied to find new cages, in: Proceedings of the 9th annual ACM-SIAM symposium on Discrete algorithms, San Francisco, California, 1998, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1998 pp. 188-191,http://dl.acm.org/ citation.cfm?id=314613.314699. · Zbl 0930.68106
[30] B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94-112, doi:10.1016/j.jsc.2013.09.003. · Zbl 1394.05079
[31] M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory30 (1999), 137-146, doi:10.1002/(sici)1097-0118(199902)30:2h137:: aid-jgt7i3.0.co;2-g. · Zbl 0918.05062
[32] J. H. Sanders, Circuit preserving edge maps II, J. Combin. Theory Ser. B 42 (1987), 146-155, doi:10.1016/0095-8956(87)90036-0. · Zbl 0582.05050
[33] R. Sousselier, Probl‘eme no. 29: le cercle des irascibles, Rev. Fr. Rech. Op´erat. 7 (1963), 405-406.
[34] C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974), 91-96, doi:10.1016/0012-365x(74)90074-0. · Zbl 0278.05110
[35] C. Thomassen, On hypohamiltonian graphs, Discrete Math. 10 (1974), 383-390, doi: 10.1016/0012-365x(74)90128-9. · Zbl 0286.05122
[36] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math.14 (1976), 377-389, doi:10.1016/0012-365x(76)90071-6. · Zbl 0322.05130
[37] C. Thomassen, Hypohamiltonian graphs and digraphs, in: Theory and Applications of Graphs, Springer, volume 642 of Lecture Notes in Mathematics, pp. 557-571, 1978, doi:10.1007/bfb0070410. · Zbl 0371.05015
[38] C. Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B30 (1981), 36-44, doi:10.1016/0095-8956(81)90089-7. · Zbl 0388.05033
[39] H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931), 378-390, doi:10.2307/ 1968197. · Zbl 0002.16101
[40] G. Wiener, New constructions of hypohamiltonian and hypotraceable graphs, 2016, submitted. · Zbl 1386.05102
[41] G. Wiener and M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011), 55-68, doi:10.1002/jgt.20513. · Zbl 1223.05168
[42] C. T. Zamfirescu, Hypohamiltonian graphs and their crossing number, Electron. J. Combin.19 (2012), #12,http://www.combinatorics.org/ojs/index. php/eljc/article/view/v19i4p12. · Zbl 1266.05079
[43] C. T. Zamfirescu, On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory79 (2015), 63-81, doi:10.1002/jgt.21815. · Zbl 1312.05076
[44] C. T. Zamfirescu and T. I. Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J. Graph Theory 55 (2007), 338-342, doi:10.1002/jgt.20241. · 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.