Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

de Wet, Johan P. ; Frick, Marietjie

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1281-1312.

Résumé

A graph G is locally P, abbreviated L, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each v ∈ V (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each v ∈ V (G). A graph G is locally locally P (abbreviated L²P) if N(v) is non-empty and induces a locally P graph for every v ∈ V (G). This concept is generalized to an arbitrary degree of nesting. For any k ≥ 0 we call a graph locally k-nested-hamiltonian if it is L^mC for m = 0, 1, . . ., k and L^kH (with L⁰C and L⁰H meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K_1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K_1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K_1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every k ≥ 1 there exist K_1,k+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.

Détail

Keywords: locally traceable, locally hamiltonian, Hamilton Cycle Problem, locally k -nested-hamiltonian, Oberly-Sumner Conjecture

Bibliographie

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[2] G. Chartrand and R. Pippert, Locally connected graphs,Čas. Pěst. Mat. 99 (1974) 158–163.

[3] G.T. Chen, A. Saito and S.L. Shan, The existence of a 2 -factor in a graph satisfying the local Chvátal-Erdős condition, SIAM J. Discrete Math. 27 (2013) 1788–1799. https://doi.org/10.1137/12090037X

[4] J.P. de Wet, Local Properties of Graphs (PhD Thesis, University of South Africa, 2016). http://uir.unisa.ac.za/bitstream/handle/10500/22278/thesisde%20wetjp.pdf?sequence=1&isAllowed=y

[5] J.P. de Wet and M. Frick, The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs, Discrete Appl. Math. 266 (2019) 291–308. https://doi.org/10.1016/j.dam.2019.02.046

[6] J.P. de Wet, M. Frick and S.A. van Aardt, Hamiltonicity of locally Hamiltonian and locally traceable graphs, Discrete Appl. Math. 236 (2018) 137–152. https://doi.org/10.1016/j.dam.2017.10.030

[7] J.P. de Wet and S.A. van Aardt, Traceability of locally traceable and locally Hamiltonian graphs, Discrete Math. Theor. Comput. Sci. 17 (2016) 245–262.

[8] M.R. Garey, D.S. Johnson and R.E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976) 704–714. https://doi.org/10.1137/0205049

[9] A. Goldner and F. Harary, Note on a smallest non-hamiltonian maximal planar graph, Bull. Malays. Math. Sci. Soc. 6 (1975) 41–42.

[10] L. Markenzon, C.M. Justel and N. Paciornik, Subclasses of k-trees: characterization and recognition, Discrete Appl. Math. 154 (2006) 818–825. https://doi.org/10.1016/j.dam.2005.05.021

[11] D.J. Oberly and D.P. Sumner, Every locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory 3 (1979) 351–356. https://doi.org/10.1002/jgt.3190030405

[12] C.M. Pareek, On the maximum degree of locally Hamiltonian non-Hamiltonian graphs, Util. Math. 23 (1983) 103–120.

[13] C.M. Pareek and Z. Skupień, On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.) 10 (1983) 9–17.

[14] D.J. Rose, On simple characterizations of k-trees, Discrete Math. 7 (1974) 317–322. https://doi.org/10.1016/0012-365X(74)90042-9

[15] Z. Skupień, Locally Hamiltonian and planar graphs, Fund. Math. 58 (1966) 193–200. https://doi.org/10.4064/fm-58-2-193-200

[16] S.A. van Aardt, M. Frick, O. Oellermann and J.P. de Wet, Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs, Discrete Appl. Math. 205 (2016) 171–179. https://doi.org/10.1016/j.dam.2015.09.022