Opuscula Math. 38, no. 3 (2018), 357-377
https://doi.org/10.7494/OpMath.2018.38.3.357
Opuscula Mathematica
Forbidden configurations for hypohamiltonian graphs
Igor Fabrici
Tomáš Madaras
Mária Timková
Abstract. A graph \(G\) is called hypohamiltonian if \(G\) is not hamiltonian, but \(G-x\) is hamiltonian for each vertex \(x\) of \(G\). We present a list of 331 forbidden configurations which do not appear in hypohamiltonian graphs.
Keywords: hypohamiltonian graph, forbidden configuration, long cycle.
Mathematics Subject Classification: 05C38, 05C45.
- R.E.L. Aldred, B.D. McKay, N.C. Wormald, Small hypohamiltonian graphs, J. Combin. Math. Combin. Comput. 23 (1997), 143-152.
- V. Chvátal, Flip-flops in hypohamiltonian graphs, Canad. Math. Bull. 16 (1973), 33-41.
- J.B. Collier, E.F. Schmeichel, Systematic searches for hypohamiltonian graphs, Networks 8 (1978), 193-200.
- J. Doyen, V. van Diest, New families of hypohamiltonian graphs, Discrete Math. 13 (1975), 225-236.
- I. Fabrici, M. Timková, T. Madaras, Local structure of planar hypohamiltonian graphs, manuscript 2017.
- J. Goedgebeur, C.T. Zamfirescu, Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017), 235-257.
- H. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann. 243 (1979), 213-216.
- J.C. Herz, J.J. Duby, F. Vigué, Recherche systématique des graphes hypohamiltoniens, [in:] P. Rosenstiehl (ed.), Theory of Graphs, Proc. International Symposium, Rome 1966, pp. 153-159.
- M. Jooyandeh, B.D. McKay, P.R.J. Östergård, V.H. Pettersson, C.T. Zamfirescu, Planar hypohamiltonian graphs on 40 vertices, J. Graph Theory 84 (2017), 121-133.
- Z. Skupień, Exponentially many hypohamiltonian snarks, Electron. Notes Discrete Math. 28 (2007), 417-424.
- C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974), 91-96.
- C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math. 14 (1976), 377-389.
- C. Thomassen, Hypohamiltonian graphs and digraphs, [in:] Y. Alavi, D.R. Lick (eds.), Theory and Applications of Graphs, Lecture Notes in Math. 642, Springer, 1978, pp. 557-571.
- D. West, Introduction to graph theory, Prentice Hall, 2011.
- G. Wiener, M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011), 55-68.
- C.T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, submitted.
- C.T. Zamfirescu, T.I. Zamfirescu, A planar hypohamiltonian graph with 48 vertices, J. Graph Theory 48 (2007), 338-342.
- Igor Fabrici
- P.J. Šafárik University in Košice, Faculty of Science, Institute of Mathematics, Jesenná 5, 040 01 Košice, Slovakia
- Tomáš Madaras
- P.J. Šafárik University in Košice, Faculty of Science, Institute of Mathematics, Jesenná 5, 040 01 Košice, Slovakia
- Mária Timková
- Technical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics, Němcovej 32, 042 00 Košice, Slovakia
- Communicated by Adam Paweł Wojda.
- Received: 2017-10-12.
- Revised: 2018-01-26.
- Accepted: 2018-02-03.
- Published online: 2018-03-19.
