Forbidden configurations for hypohamiltonian graphs

• Autorzy: Fabrici I. , Madaras T. , Timkova M.

Identyfikatory

DOI

10.7494/OpMath.2018.38.3.357

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypohamiltonian graph; forbidden configuration; long cycle

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2018
• Tom: Vol. 38, no. 3
• Strony: 357--377
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Fabrici I.

• P.J. Śafarik University in Kosice Faculty of Science Institute of Mathematics Jesenna 5, 040 01 Kosice, Slovakia

autor

Madaras T.

• P.J. Śafarik University in Kosice Faculty of Science Institute of Mathematics Jesenna 5, 040 01 Kosice, Slovakia

autor

Timkova M.

• Technical University of Kosice Faculty of Electrical Engineering and Informatics Department of Mathematics and Theoretical Informatics Nemcovej 32, 042 00 Kosice, Slovakia

Bibliografia

• [1] R.E.L. Aldred, B.D. McKay, N.C. Wormald, Small hypohamiltonian graphs, J. Combin. Math. Combin. Comput. 23 (1997), 143-152.
• [2] V. Chvatal, Flip-flops in hypohamiltonian graphs, Canad. Math. Bull. 16 (1973), 33-41.
• [3] J.B. Collier, E.F. Schmeichel, Systematic searches for hypohamiltonian graphs, Networks 8 (1978), 193-200.
• [4] J. Doyen, V. van Diest, New families of hypohamiltonian graphs, Discrete Math. 13 (1975), 225-236.
• [5] I. Fabrici, M. Timkova, T. Madaras, Local structure of planar hypohamiltonian graphs, manuscript 2017.
• [6] J. Goedgebeur, C.T. Zamfirescu, Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017), 235-257.
• [7] H. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann. 243 (1979), 213-216.
• [8] J.C. Herz, J.J. Duby, F. Vigue, Recherche systematique des graphes hypohamiltoniens, [in:] P. Rosenstiehl (ed.), Theory of Graphs, Proc. International Symposium, Rome 1966, pp. 153-159.
• [9] M. Jooyandeh, B.D. McKay, P.R.J. Óstergard, V.H. Pettersson, C.T. Zamfirescu, Planar hypohamiltonian graphs on Ą0 vertices, J. Graph Theory 84 (2017), 121-133.
• [10] Z. Skupień, Exponentially many hypohamiltonian snarks, Electron. Notes Discrete Math. 28 (2007), 417-424.
• [11] C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Math. 9 (1974), 91-96.
• [12] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math. 14 (1976), 377-389.
• [13] 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.
• [14] D. West, Introduction to graph theory, Prentice Hall, 2011.
• [15] G. Wiener, M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011), 55-68.
• [16] C.T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, submitted.
• [17] C.T. Zamfirescu, T.I. Zamfirescu, A planar hypohamiltonian graph with Ą8 vertices, J. Graph Theory 48 (2007), 338-342.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).