A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
Author(s) -
Long Tang,
Elkin Vumar
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2124
Subject(s) - mathematics , combinatorics , conjecture , neighbourhood (mathematics) , vertex connectivity , induced subgraph , pancyclic graph , graph , hamiltonian path , distance hereditary graph , discrete mathematics , vertex (graph theory) , line graph , graph power , 1 planar graph , mathematical analysis
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom