1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1281 - 1312
Received: 08 Jan 2019
Accepted: 03 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A graph G is locally 𝒫, 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 𝒫. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each vV (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each vV (G). A graph G is locally locally 𝒫 (abbreviated L2𝒫) if N(v) is non-empty and induces a locally 𝒫 graph for every vV (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 LmC for m = 0, 1, . . ., k and LkH (with L0C and L0H 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 K1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K1,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 K1,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 K1,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.

Keywords

MSC 2010

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

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

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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. Search in Google Scholar

[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 Search in Google Scholar

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

[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 Search in Google Scholar

[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 Search in Google Scholar

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

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

[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 Search in Google Scholar

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

[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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo