Structural and computational results on platypus graphs. (English) Zbl 1462.05110

Summary: A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions regarding longest paths and longest cycles, for instance hypohamiltonian, leaf-stable, and maximally non-hamiltonian graphs.
In this paper, we first investigate cubic platypus graphs, covering all orders for which such graphs exist: in the general and polyhedral case as well as for snarks. We then present (not necessarily cubic) platypus graphs of girth up to 16 – whereas no hypohamiltonian graphs of girth greater than 7 are known – and study their maximum degree, generalising two theorems of G. Chartrand et al. [in: Second international conference on combinatorial mathematics, New York, 1978, Ann. New York Acad. Sci. 319, 130–135 (1979; Zbl 0481.05039)]. Using computational methods, we determine the complete list of all non-isomorphic platypus graphs for various orders and girths. Finally, we address two questions raised by the third author in [J. Graph Theory 86, No. 2, 223–243 (2017; Zbl 1370.05115)].


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)
Full Text: DOI arXiv


[1] Alspach, B. R., The classification of hamiltonian generalized Petersen graphs, J. Combin. Theory, Ser. B, 34, 293-312 (1983) · Zbl 0516.05034
[2] Boben, M.; Pisanski, T.; Žirnki, A., I-graphs and the corresponding configurations, J. Combin. Des., 13, 406-424 (2005) · Zbl 1076.05065
[3] Bondy, J. A., Variations on the hamiltonian theme, Canad. Math. Bull., 15, 57-62 (1972) · Zbl 0238.05115
[4] Available at http://hog.grinvin.org/ · Zbl 1292.05254
[5] Brinkmann, G.; Goedgebeur, J.; Hägglund, J.; Markström, K., Generation and properties of snarks, J. Combin. Theory, Ser. B, 103, 468-488 (2013) · Zbl 1301.05119
[6] Brinkmann, G.; McKay, B. D., Construction of planar triangulations with minimum degree 5, Discrete Math., 301, 147-163 (2005) · Zbl 1078.05022
[7] Brinkmann, G.; McKay, B. D., Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem., 58, 323-357 (2007) · Zbl 1164.68025
[8] Chartrand, G.; Gould, R. J.; Kapoor, S. F., On homogeneously traceable nonhamiltonian graphs, Ann. N. Y. Acad. Sci., 319, 130-135 (1979) · Zbl 0481.05039
[9] Clark, L.; Entringer, R., Smallest maximally nonhamiltonian graphs, Period. Math. Hung., 14, 57-68 (1983) · Zbl 0489.05038
[10] Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., 56, 413-455 (1950) · Zbl 0040.22803
[11] Ferrero, D.; Hanusch, S., Component connectivity of generalized Petersen graphs, Internat. J. Comput. Math., 91, 1940-1963 (2014) · Zbl 1408.05077
[12] J. Goedgebeur, C.T. Zamfirescu, Homepage of a generator for hypohamiltonian graphs, 2016, http://caagt.ugent.be/hypoham/.
[13] Goedgebeur, J.; Zamfirescu, C. T., Improved bounds for hypohamiltonian graphs, Ars Math. Contemp., 13, 235-257 (2017) · Zbl 1380.05034
[14] Goedgebeur, J.; Zamfirescu, C. T., On hypohamiltonian snarks and a theorem of Fiorini, Ars Math. Contemp., 14, 227-249 (2018) · Zbl 1395.05044
[15] Holton, D. A.; McKay, B. D., The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combin. Theory, Ser. B, 45, 305-319 (1988) · Zbl 0607.05051
[16] Holton, D. A.; Sheehan, J., The Petersen graph, chapter 7: Hypohamiltonian graphs (1993), Cambridge University Press: Cambridge University Press New York · Zbl 0781.05001
[17] Máčajová, E.; Škoviera, M., Infinitely many hypohamiltonian cubic graphs of girth 7, Graphs Combin., 27, 231-241 (2011) · Zbl 1235.05085
[18] B.D. McKay, nauty user’s guide (version 2.6), 2017. Technical Report TR-CS-90-02, Department of Computer Science, Australian National University. The latest version of the software is available at http://cs.anu.edu.au/ bdm/nauty.
[19] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[20] M.Sc. thesis (in Dutch).
[21] Watkins, M. E., A theorem on Tait colorings with an application to generalized Petersen graphs, J. Combin. Theory, 6, 152-164 (1969) · Zbl 0175.50303
[22] Zamfirescu, C. T., On non-hamiltonian graphs for which every vertex-deleted subgraph is traceable, J. Graph Theory, 86, 223-243 (2017) · Zbl 1370.05115
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.