A NOTE ON CYCLES IN LOCALLY HAMILTONIAN AND LOCALLY HAMILTON-CONNECTED GRAPHS

作者：Tang, Long; Vumar, Elkin^*

来源：Discussiones Mathematicae - Graph Theory, 2020, 40(1): 77-84.

DOI：10.7151/dmgt.2124

• locally connected
• locally Hamiltonian
• locally Hamilton-connected
• fully cycle extendability
• weakly pancyclicity

Let P be a property of a graph. A graph G is said to be locally P, if the subgraph induced by the open neighbourhood of every vertex in G has property P. Ryjacek 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 vertical bar V(G)vertical bar - 5 is weakly pancyclic. In this note, we improve this result by showing that such a graph with maximum degree at least vertical bar V (G)vertical bar - 6 is weakly pancyclic. Furthermore, we show that a connected, locally Hamilton-connected graph with maximum degree at most 7 is fully cycle extendable.

• 出版日期2020
• 单位新疆大学