×

zbMATH — the first resource for mathematics

Improved bounds for hypo-Hamiltonian graphs. (English) Zbl 1380.05034
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.

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)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [1] R. E. L. Aldred, S. Bau, D. Holton and B. D. McKay, Nonhamiltonian 3-connectedcubic planar graphs, SIAM J. Discrete Math. 13 (2000), 25-32, doi:10.1137/S0895480198348665. · Zbl 0941.05041
[2] [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] [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] [4] J. M. Boyer and W. J. Myrvold, On the cutting edge: simplified O(n) planarity byedge addition, J. Graph Algorithms Appl. 8 (2004), 241-273, doi:10.7155/jgaa.00091. · Zbl 1086.05067
[5] [5] G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. M´elot, House of Graphs: adatabase 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] [6] G. Brinkmann and J. Goedgebeur, Generation of cubic graphs and snarks with largegirth, J. Graph Theory (2017), doi:10.1002/jgt.22125. · Zbl 1370.05198
[7] [7] G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markstr¨om, Generation and prop-erties of snarks, J. Combin. Theory Ser. B 103 (2013), 468-488, doi:10.1016/j.jctb.2013.05.001. · Zbl 1301.05119
[8] [8] G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Dis-crete 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] [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] [10] G. Chartrand, S. F. Kapoor and D. R. Lick, n-hamiltonian graphs, J. CombinatorialTheory9 (1970), 308-312, doi:10.1016/s0021-9800(70)80069-2.J. Goedgebeur and C. T. Zamfirescu: Improved bounds for hypohamiltonian graphs255 · Zbl 0204.57005
[11] [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] [12] J. B. Collier and E. F. Schmeichel, New flip-flop constructions for hypohamiltoniangraphs, Discrete Math. 18 (1977), 265-271, doi:10.1016/0012-365x(77)90130-3.
[13] [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] [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.
[15] [15] J. Goedgebeur and C. T. Zamfirescu, New results on hypohamiltonian and almosthypohamiltonian graphs,arXiv:1606.06577 · Zbl 1395.05044
[16] [16] J. Goedgebeur and C. T. Zamfirescu, Hypohamiltonian graphs, 2016, homepage ofGenHypohamiltonian,http://caagt.ugent.be/hypoham/.
[17] [17] B. Gr¨unbaum, Vertices missed by longest paths or circuits, J. Combin. Theory Ser. A17 (1974), 31-38, doi:10.1016/0097-3165(74)90025-9.
[18] [18] W. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann. 243(1979), 213-216, doi:10.1007/bf01424541. · Zbl 0396.05032
[19] [19] J. C. Herz, J. J. Duby and F. Vigu´e, Recherche syst´ematique des graphes hypohamil-toniens, in: P. Rosentiehl (ed.), Theory of Graphs: International Symposium, Rome,July 1966, Dunod, Paris, 1967 pp. 153-159.
[20] [20] D. A. Holton and B. D. McKay, The smallest non-hamiltonian 3-connected cubicplanar 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] [21] D. A. Holton and J. Sheehan, The Petersen Graph, volume 7 of Australian Mathe-matical Society Lecture Series, Cambridge University Press, New York, 1993, doi:10.1017/cbo9780511662058.
[22] [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] [23] F. Kardoˇs, A computer-assisted proof of Barnette’s conjecture: not only fullerenegraphs are hamiltonian,arXiv:1409.2440
[24] [24] E. M´aˇcajov´a and M. ˇSkoviera, Infinitely many hypohamiltonian cubic graphs of girth7, Graphs Combin. 27 (2011), 231-241, doi:10.1007/s00373-010-0968-z. · Zbl 1235.05085
[25] [25] B. D. McKay, Combinatorial Data - Graphs, page with hypohamiltonian graphs,http://users.cecs.anu.edu.au/˜bdm/data/graphs.html.
[26] [26] B. D. McKay, nauty User’s Guide (Version 2.5), technical report TR-CS-90-02, De-partment of Computer Science, Australian National University,http://cs.anu.edu.au/˜bdm/nauty.256Ars Math. Contemp. 13 (2017) 235-257
[27] [27] B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), 306-324, doi:10.1006/jagm.1997.0898. · Zbl 0894.68107
[28] [28] B. D. McKay, Hypohamiltonian planar cubic graphs with girth five, J. Graph Theory(2016), doi:10.1002/jgt.22043.
[29] [29] B. D. McKay, W. Myrvold and J. Nadon, Fast backtracking principles applied to findnew cages, in: Proceedings of the 9th annual ACM-SIAM symposium on Discrete al-gorithms, San Francisco, California, 1998, Society for Industrial and Applied Math-ematics, Philadelphia, Pennsylvania, 1998 pp. 188-191,http://dl.acm.org/citation.cfm?id=314613.314699. · Zbl 0930.68106
[30] [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] [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.
[32] [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.
[33] [33] R. Sousselier, Probl‘eme no. 29: le cercle des irascibles, Rev. Fr. Rech. Op´erat. 7(1963), 405-406.
[34] [34] C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974),91-96, doi:10.1016/0012-365x(74)90074-0.
[35] [35] C. Thomassen, On hypohamiltonian graphs, Discrete Math. 10 (1974), 383-390, doi:10.1016/0012-365x(74)90128-9.
[36] [36] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Dis-crete Math.14 (1976), 377-389, doi:10.1016/0012-365x(76)90071-6.
[37] [37] C. Thomassen, Hypohamiltonian graphs and digraphs, in: Theory and Applications ofGraphs, Springer, volume 642 of Lecture Notes in Mathematics, pp. 557-571, 1978,doi:10.1007/bfb0070410.
[38] [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.
[39] [39] H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931), 378-390, doi:10.2307/1968197.
[40] [40] G. Wiener, New constructions of hypohamiltonian and hypotraceable graphs, 2016,submitted.
[41] [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] [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.J. Goedgebeur and C. T. Zamfirescu: Improved bounds for hypohamiltonian graphs257 · Zbl 1266.05079
[43] [43] C. T. Zamfirescu, On hypohamiltonian and almost hypohamiltonian graphs, J. GraphTheory79 (2015), 63-81, doi:10.1002/jgt.21815. · Zbl 1312.05076
[44] [44] C. T. Zamfirescu and T. I. Zamfirescu, A planar hypohamiltonian graph with 48 ver-tices, 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. 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.