×
Fabrici, Igor; Madaras, Tomáš; Timková, Mária; Van Cleemput, Nico; Zamfirescu, Carol T.

Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian. (English) Zbl 1462.05206

Appl. Math. Comput. 392, Article ID 125714, 12 p. (2021).
Summary: A graph \(G\) is perihamiltonian if \(G\) itself is non-hamiltonian, yet every edge-contracted subgraph of \(G\) is hamiltonian. These graphs form a superclass of the hypohamiltonian graphs. By applying a recent result of Wiener on path-critical graphs, we prove the existence of infinitely many perihamiltonian graphs of connectivity \(k\) for any \(k \geq 2\). We also show that every planar perihamiltonian graph of connectivity \(k\) contains a vertex of degree \(k\). This strengthens a theorem of Thomassen, and entails that if in a polyhedral graph of minimum degree at least 4 the set of vertices whose removal yields a non-hamiltonian graph is independent, the graph itself must be hamiltonian. Finally, while we here prove that there are infinitely many polyhedral perihamiltonian graphs containing no adjacent cubic vertices, whether an analogous result holds for the hypohamiltonian case remains open.

Cited in 2 Documents

MSC:

05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C40 Connectivity

Keywords:

non-Hamiltonian; perihamiltonian; hypohamiltonian

Software:

Traces; GENREG; GenHypohamiltonian; nauty
Cite Review PDF
Full Text: DOI Link

References:

[1] Bondy, J. A., Variations on the hamiltonian theme, Canad. Math. Bull., 15, 57-62 (1972) · Zbl 0238.05115
[2] Available at http://hog.grinvin.org. · Zbl 1292.05254
[3] See http://cs.anu.edu.au/ bdm/index.html.
[4] P39. · Zbl 1409.05122
[5] Chvátal, V., Flip-flops in hypohamiltonian graphs, Canad. Math. Bull., 16, 33-41 (1973) · Zbl 0253.05142
[6] Collier, J. B.; Schmeichel, E. F., Systematic searches for hypohamiltonian graphs, Networks, 8, 193-200 (1978) · Zbl 0384.05046
[7] Goedgebeur, J.; Zamfirescu, C. T., Improved bounds for hypohamiltonian graphs, Ars Math. Contemp., 13, 235-257 (2017) · Zbl 1380.05034
[8] 5 · Zbl 1417.05114
[9] Holton, D. A.; Sheehan, J., The Petersen Graph, Chapter 7: Hypohamiltonian Graphs (1993), Cambridge University Press: Cambridge University Press New York · Zbl 0781.05001
[10] Univ. Waterloo
[11] Hsu, L.-H.; Lin, C. K., Graph Theory and Interconnection Networks (2008), CRC Press: CRC Press Boca Raton
[12] Jooyandeh, M.; McKay, B. D.; Östergård, P. R.J.; Pettersson, V. H.; Zamfirescu, C. T., Planar hypohamiltonian graphs on 40 vertices, J. Graph Theory, 84, 121-133 (2017) · Zbl 1356.05029
[13] McKay, B. D.; Piperno, A., Practical graph isomorphism II, J. Symbolic Comput., 60, 94-112 (2013) · Zbl 1394.05079
[14] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146 (1999) · Zbl 0918.05062
[15] A. Neyt, Platypus Graphs: Structure and Generation, Ghent University, 2017 (in Dutch). MSc Thesis.
[16] Sanders, D. P., On paths in planar graphs, J. Graph Theory, 24, 341-345 (1997) · Zbl 0880.05059
[17] Thomassen, C., On hypohamiltonian graphs, Discrete Math., 10, 383-390 (1974) · Zbl 0286.05122
[18] Thomassen, C., Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math., 14, 377-389 (1976) · Zbl 0322.05130
[19] Thomassen, C., Hypohamiltonian graphs and digraphs, LNCS, 642, 557-571 (1978) · Zbl 0371.05015
[20] Thomassen, C., Planar cubic hypohamiltonian and hypotraceable graphs, J. Combin. Theory, Ser. B, 30, 36-44 (1981) · Zbl 0388.05033
[21] Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403
[22] Whitney, H., A theorem on graphs, Ann. Math., 32, 378-390 (1931) · JFM 57.0727.03
[23] Proc. EuroComb 2015 (eds.: J. Neš etřil, O. Serra, J. A. Telle). · Zbl 1346.05138
[24] Wiener, G., Leaf-critical and leaf-stable graphs, J. Graph Theory, 84, 443-459 (2017) · Zbl 1359.05072
[25] Wiener, G.; Araya, M., On planar hypohamiltonian graphs, J. Graph Theory, 67, 55-68 (2011) · Zbl 1223.05168
[26] Zamfirescu, C. T., Hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory, 79, 63-81 (2015) · Zbl 1312.05076
[27] 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
[28] Zamfirescu, C. T., Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory, 90, 189-207 (2019) · Zbl 1466.05038
[29] C.T. Zamfirescu, On the hamiltonicity of a planar graph and its vertex-deleted subgraphs. Submitted. · Zbl 1528.05039
[30] Zamfirescu, C. T.; Zamfirescu, T. I., Every graph occurs as an induced subgraph of some hypohamiltonian graph, J. Graph Theory, 88, 551-557 (2018) · Zbl 1393.05095
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.