Full cycle extendability of locally connected $K_{1,4}$-restricted graphs

P. A. Irzhavski ; Yu. L. Orlovich

Trudy Instituta matematiki, Tome 20 (2012) no. 2, pp. 36-50.

Résumé

In this paper we show that a connected locally connected $K_{1,4}$-restricted graph on at least three vertices is either fully cycle extendable or isomorphic to one of the five exceptional (non-Hamiltonian) graphs. This result generalizes several known results on the existence of Hamiltonian cycles in locally connected graphs. We also propose a polynomial time algorithm for finding a Hamiltonian cycle in graphs under consideration.

Bibliographie

[1] Karp R. M., “Reducibility among combinatorial problems”, Proc. of a Symp. on the Complexity of Computer Computations, New York, 1972, 85–103 | DOI | MR

[2] Garey M. R., Johnson D. S., Tarjan R. E., “The planar Hamiltonian circuit problem is NP-complete”, SIAM J. Comput., 5 (1976), 704–714 | DOI | MR | Zbl

[3] Benediktovich V. I., Sarvanov V. I., “O gamiltonovosti kubicheskikh planarnykh grafov”, Dokl. AN Belarusi, 41:1 (1997), 34–37 | MR | Zbl

[4] Akiyama T., Nishizeki T., Saito N., “NP-completeness of the Hamiltonian cycle problem for bipartite graphs”, J. Inf. Process, 3 (1980), 73–76 | MR | Zbl

[5] Chvátal V., “Hamiltonian cycles”, The traveling salesman problem. A guided tour of combinatorial optimization, Wiley–Intersci. Ser. Discrete Math., Wiley, Chichester, 1985, 403–429 | MR

[6] Picouleau C., “Complexity of the hamiltonian cycle in regular graph problem”, Theor. Comput. Sci., 131 (1994), 463–473 | DOI | MR | Zbl

[7] Itai A., Papadimitriou C. H., Szwarcfiter J. L., “Hamilton paths in grid graphs”, SIAM J. Comput., 11 (1982), 676–686 | DOI | MR | Zbl

[8] Gordon V. S., Orlovich Y. L., Werner F., “Hamiltonian properties of triangular grid graphs”, Discrete Math., 308 (2008), 6166–6188 | DOI | MR | Zbl

[9] Arkin E. M. et al., “Not being (super)thin or solid is hard: A study of grid Hamiltonicity”, Comput. Geom., 42 (2009), 582–605 | DOI | MR | Zbl

[10] Gordon V. S. et al., “Hamiltonian properties of locally connected graphs with bounded vertex degree”, Discrete Appl. Math., 159 (2011), 1759–1774 | DOI | MR | Zbl

[11] Müller H., “Hamiltonian circuits in chordal bipartite graphs”, Discrete Math., 156 (1996), 291–298 | DOI | MR

[12] Bertossi A. A., “The edge Hamiltonian path problem is NP-complete”, Inf. Process. Lett., 13 (1981), 157–159 | DOI | MR | Zbl

[13] Corneil D. G., Lerchs H., Stewart Burlingham L., “Complement reducible graphs”, Discrete Appl. Math., 3 (1981), 163–174 | DOI | MR | Zbl

[14] Keil J. M., “Finding Hamiltonian circuits in interval graphs”, Inf. Process. Lett., 20 (1985), 201–206 | DOI | MR | Zbl

[15] Hung R.-W., Chang M.-S., “An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs”, Theor. Comput. Sci., 412 (2011), 5351–5373 | DOI | MR | Zbl

[16] Deogun J. S., Steiner G., “Polynomial algorithms for hamiltonian cycle in cocomparability graphs”, SIAM J. Comput., 23 (1994), 520–552 | DOI | MR | Zbl

[17] Chiba N., Nishizeki T., “The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs”, J. Algorithms, 10 (1989), 187–211 | DOI | MR | Zbl

[18] Oberly D. J., Sumner D. P., “Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian”, J. Graph Theory, 3 (1979), 351–356 | DOI | MR | Zbl

[19] Hendry G. R. T., “Extending cycles in graphs”, Discrete Math., 85 (1990), 59–72 | DOI | MR | Zbl

[20] Zhang C.-Q., “Cycles of given length in some $K_{1,3}$-free graphs”, Discrete Math., 78 (1989), 307–313 | DOI | MR | Zbl

[21] Chartrand G., Gould R. J., Polimeni A. D., “A note on locally connected and hamiltonian-connected graphs”, Isr. J. Math., 33 (1979), 5–8 | DOI | MR | Zbl

[22] Clark L., “Hamiltonian properties of connected locally connected graphs”, Congr. Numer., 32 (1981), 199–204 | MR | Zbl

[23] Pronin F. V., “Lineinyi algoritm postroeniya gamiltonova tsikla v lokalno svyaznom grafe treugolnoi reshetki”, Vestn. BGU. Ser. 1, 2011, no. 1, 90–96 | MR | Zbl

[24] Bertossi A. A., “Finding Hamiltonian circuits in proper interval graphs”, Inf. Process. Lett., 17 (1983), 97–101 | DOI | MR | Zbl

[25] Brandstädt A., Dragan F. F., Köhler E., “Linear time algorithms for Hamiltonian problems on (claw, net)-free graphs”, SIAM J. Comput., 30 (2000), 1662–1677 | DOI | MR

[26] Rao L., “Finding Hamiltonian cycles in \{quasi-claw, $K_{1,5},$ $K_{1,5}+e$\}-free graphs with bounded Dilworth numbers”, Discrete Math., 309 (2009), 2555–2558 | DOI | MR | Zbl

[27] Blazewicz J., Kasprzak M., Leroy-Beaulieu B., de Werra D., “Finding Hamiltonian circuits in quasi-adjoint graphs”, Discrete Appl. Math., 156 (2008), 2573–2580 | DOI | MR | Zbl

[28] Hung R.-W., Chang M.-S., “Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs”, Theor. Comput. Sci., 341 (2005), 411–440 | DOI | MR | Zbl

[29] Faudree R., Flandrin E., Ryjáček Z., “Claw-free graphs — a survey”, Discrete Math., 164 (1997), 87–147 | DOI | MR | Zbl

[30] Ryjáček Z., “Hamiltonian circuits in $N_2$-locally connected $K_{1,3}$-free graphs”, J. Graph Theory, 14 (1990), 321–331 | DOI | MR | Zbl

[31] Zhan M., “Vertex pancyclicity in quasi claw-free graphs”, Discrete Math., 307 (2007), 1679–1683 | DOI | MR | Zbl

[32] Li M. et al., “Quadrangularly connected claw-free graphs”, Discrete Math., 307 (2007), 1205–1211 | DOI | MR | Zbl

[33] Emelichev V. A. i dr., Lektsii po teorii grafov, M., 1990

[34] Wang J., Teng Y., “$K_{1,p}$-restricted graphs”, Adv. Math., 35 (2006), 657–662 (in Chinese) | MR

[35] Wang J., Li M., “Fully cycle extendability of $K_{1,4}$-restricted graphs”, Discrete Math., 309 (2009), 4011–4016 | DOI | MR | Zbl

[36] Chartrand G., Pippert R. E., “Locally connected graphs”, Čas. Pěst. Mat., 99 (1974), 158–163 | MR | Zbl

[37] Ryjáček Z., “Almost claw-free graphs”, J. Graph Theory, 18 (1994), 469–477 | DOI | MR | Zbl

[38] Li M.-C., Corneil D. G., Mendelsohn E., “Pancyclicity and NP-completeness in planar graphs”, Discrete Appl. Math., 98 (2000), 219–225 | DOI | MR | Zbl