Article in volume
Authors:
Title:
Nested locally Hamiltonian graphs and the Oberly-Sumner Conjecture
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1281-1312
Received: 2019-01-08 , Revised: 2020-07-03 , Accepted: 2020-07-03 , Available online: 2020-07-21 , https://doi.org/10.7151/dmgt.2346
Abstract:
A graph $G$ is locally $\cal P$, abbreviated $L{\cal P}$, if for every
vertex $v$ in $G$ the open neighbourhood $N(v)$ of $v$ is non-empty and induces
a graph with property $\cal P$. Specifically, a graph $G$ without isolated
vertices is locally connected ($LC$) if $N(v)$ induces a connected graph
for each $v\in V(G)$, and locally hamiltonian ($LH$) if $N(v)$ induces a
hamiltonian graph for each $v\in V(G)$. A graph $G$ is locally locally
$\cal P$ (abbreviated $L^2{\cal P}$) if $N(v)$ is non-empty and induces a
locally $\cal P$ graph for every $v\in V(G)$. This concept is generalized to
an arbitrary degree of nesting. For any $k\geq 0$ we call a graph locally
$k$-nested-hamiltonian if it is $L^mC$ for $m=0,1,\ldots, k$ and $L^kH$ (with
$L^0C$ and $L^0H$ 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\geq 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\geq 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\geq 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.
Keywords:
locally traceable, locally hamiltonian, Hamilton Cycle Problem, locally $k$-nested-hamiltonian, Oberly-Sumner Conjecture
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- G. Chartrand and R. Pippert, Locally connected graphs, Čas. Pěst. Mat. 99 (1974) 158–163.
- 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 - J.P. de Wet, Local Properties of Graphs (PhD Thesis, University of South Africa, 2016).
http://uir.unisa.ac.za/bitstream/handle/10500/22278/thesis_de \%20wet_jp.pdf?sequence=1&isAllowed=y - 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 - 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 - 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.
- 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 - A. Goldner and F. Harary, Note on a smallest non-hamiltonian maximal planar graph, Bull. Malays. Math. Sci. Soc. 6 (1975) 41–42.
- 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 - 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 - C.M. Pareek, On the maximum degree of locally Hamiltonian non-Hamiltonian graphs, Util. Math. 23 (1983) 103–120.
- C.M. Pareek and Z. Skupień, On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.) 10 (1983) 9–17.
- 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 - Z. Skupień, Locally Hamiltonian and planar graphs, Fund. Math. 58 (1966) 193–200.
https://doi.org/10.4064/fm-58-2-193-200 - 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
Close