Authors:
L. Tang, E. Vumar
Title:
A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
Source:
Discussiones Mathematicae Graph Theory
Received 22.06.2017, Revised 05.02.2018, Accepted 05.02.2018, doi: 10.7151/dmgt.2124

Abstract:
Let 𝒫 be a property of a graph. A graph G is said to be locally 𝒫, if the subgraph induced by the open neighbourhood of every vertex in G has property 𝒫. Ryjáček conjectures that every connected, locally connected graph is weakly pancyclic. Motivated by the above conjecture, van Aardt et al. [S.A.van Aardt, M. Frick, O.R. 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] investigated the global cycle structures in connected, locally traceable/Hamiltonian graphs. Among other results, they proved that a connected, locally Hamiltonian graph G with maximum degree at least |V(G)|-5 is weakly pancyclic. In this note, we improve this result by showing that such a graph with maximum degree at least |V(G)|-6 is weakly pancyclic. Furthermore, we show that a connected, locally Hamilton-connected graph with maximum degree at most 7 is fully cycle extendable.
Keywords:
locally connected, locally Hamiltonian, locally Hamilton-connected, fully cycle extendability, weakly pancyclicity

Links:
PDF