On Finding Hamiltonian Cycles in Barnette Graphs

• Autorzy: Bagheri Gh. Behrooz , Feder Tomas , Fleischner Herbert , Subi Carlos

Identyfikatory

DOI

10.3233/FI-222139

• Języki publikacji: EN

Abstrakty

EN

In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2−factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3−connected planar cubic bipartite graphs is an NP-complete problem.

Słowa kluczowe

EN

Barnette’s Conjecture; eulerian plane graph; hamiltonian cycle; spanning tree of faces; A−trail.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 188 nr 1
• Strony: 1--14
• Opis fizyczny: Bibliogr. 22 poz.,

Twórcy

autor

Bagheri Gh. Behrooz

• Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11, 1040 Vienna, Austria

autor

Feder Tomas

• Computer Science Department Stanford University Stanford, California 94305, USA

autor

Fleischner Herbert

• Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11, 1040 Vienna, Austria

autor

Subi Carlos

Bibliografia

• [1] Bagheri Gh B, Feder T, Fleischner H, Subi C. Hamiltonian cycles in planar cubic graphs with facial 2−factors, and a new partial solution of Barnette’s Conjecture. J. Graph Theory, 2021. 96(2):269-288. doi:10.1002/jgt.22612.
• [2] Tait PG. Listing’s Topologie. Philosophical Magazine (5th ser.), 1884. 17:30-46. Reprinted in Scientific Papers, Vol. II, pp. 85-98.
• [3] Petersen J. Sur le th´eor`eme de Tait. Interm´ed. Math., 1898. 28:225-227.
• [4] Tutte WT. ON HAMILTONIAN CIRCUITS. J. London Math. Soc., 1946. 21(2):98-101.
• [5] Tutte WT. On the 2−factors of bicubic graphs. Discrete Math., 1971. 1(2):203-208.
• [6] Horton JD. On two-factors of bipartite regular graphs. Discrete Math., 1982. 41(1):35-41. doi:10.1016/0012-365X(82)90079-6.
• [7] Barnette DW. Conjecture 5. In: In William T. Tutte, ed., Recent Progress in Combinatorics. Proceedings of the 3rd Waterloo Conference on Combinatorics, vol. 3. 1969 p. 343.
• [8] Holton DA, Manvel B, McKay BD. Hamiltonian cycles in cubic 3−connected bipartite planar graphs. Journal of Combinatorial Theory, Series B, 1985. 38(3):279-297. doi:10.1016/0095-8956(85)90072-3.
• [9] Goodey PR. Hamiltonian circuits in polytopes with even sides. Israel Journal of Mathematics, 1975. 22:52-56. doi:10.1007/BF02757273.
• [10] Takanori A, Takao N, Nobuji S. NP-completeness of the Hamiltonian cycle problem for bipartite graphs. Journal of Information Processing Abstract, 1980. 3:73-76. ID: 60323180.
• [11] Feder T, Subi C. On Barnette’s Conjecture. Electronic Colloquium on Computational Complexity, TR06-015, 2006.
• [12] Bondy JA, Murty USR. Graph Theory, Graduate Texts in Mathematics, 244. Springer, New York, 2008. ISBN-10:1849966907, 13:978-1849966900.
• [13] Fleischner H. Eulerian graphs and related topics. Part 1, Volume 1, Ann. of Discrete Math., 45, 1990. ISBN-9780444891105, 9780080867908.
• [14] Fleischner H, Hobbs AM, Tapfuma MM. Hamiltonicity in vertex envelopes of plane cubic graphs. Discrete Math., 2009. 309(14):4793-4809. doi:10.1016/j.disc.2008.06.011.
• [15] Fowler PW. How unusual is C60? Magic numbers for carbon clusters. Chem. Phys. Lett., 1986. 131(6):444-450. doi:10.1016/0009-2614(86)80563-2.
• [16] Kardoˇs F. A computer-assisted proof of Barnette-Goodey Conjecture: Not only fullerene graphs are Hamiltonian. URL URL https://arxiv.org/pdf/1409.2440v2.pdf.
• [17] Yoshida M, Fujita M, Fowler PW, Kirby EC. Non-bonding orbitals in graphite, carbon tubules, toroids and fullerenes. J. Chem. Soc., Faraday Trans., 1997. 93:1037-1043. doi:10.1039/A607401D.
• [18] Andersen LD, Fleischner H. The NP-completeness of finding A−trails in Eulerian graphs and of finding spanning trees in hypergraphs. Discrete Appl. Math., 1995. 59:203-214. doi:10.1016/0166-218X(95)80001-K.
• [19] Andersen LD, Fleischner H, Regner S. Algorithms and outerplanar conditions for A−trails in plane Eulerian graphs. Discrete Appl. Math., 1998. 85:99-112. ISSN-0166-218X.
• [20] Gabow HN, Stallmann M. Efficient algorithms for graphic intersection and parity. In: Proc. 12th Int. Conf. Automata, Languages, and Programming, volume 194. Springer-Verlag LNCS, 1985 pp. 210-220. doi:10.1007/BFb0015746.
• [21] Lov´asz L. Matroid matching and some applications. J. Combinatorial Theory Ser. B, 1980. 28:208-236. doi:10.1016/0095-8956(80)90066-0.
• [22] Garey MR, Johnson DS, Tarjan RE. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 1976. 5:704-714. doi:10.1137/0205049.