Geodesic
A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 77-84.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2020_40_1_a5,
     author = {Tang, Long and Vumar, Elkin},
     title = {A {Note} on {Cycles} in {Locally} {Hamiltonian} and {Locally} {Hamilton-Connected} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {77--84},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a5/}
}
TY  - JOUR
AU  - Tang, Long
AU  - Vumar, Elkin
TI  - A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 77
EP  - 84
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a5/
LA  - en
ID  - DMGT_2020_40_1_a5
ER  - 
%0 Journal Article
%A Tang, Long
%A Vumar, Elkin
%T A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 77-84
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a5/
%G en
%F DMGT_2020_40_1_a5
Tang, Long; Vumar, Elkin. A Note on Cycles in Locally Hamiltonian and Locally Hamilton-Connected Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 77-84. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a5/

[1] A. Adamaszek, M. Adamaszek, M. Mnich and J.M. Schmidt, Lower bounds for locally highly connected graphs, Graphs Combin. 32 (2016) 1641–1650. doi:10.1007/s00373-016-1686-y

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[3] A. Borchert, S. Nicol and O.R. Oellermann, Global cycle properties of locally isometric graphs, Discrete Appl. Math. 205 (2016) 16–26. doi:10.1016/j.dam.2016.01.026

[4] C. Brause, D. Rautenbach and I. Schiermeyer, Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability, Discrete Math. 340 (2017) 596–606. doi:10.1016/j.disc.2016.11.035

[5] G. Chartrand and R.E. Pippert, Locally connected graphs, Časopis Pěst. Mat. 99 (1974) 158–163.

[6] J.P. de Wet and S.A. van Aardt, Traceablity of locally Hamiltonian and locally traceable graphs, Discrete Math. Theor. Comput. Sci. 17 (2016) 245–262.

[7] 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. doi:10.1016/j.dam.2017.10.030

[8] G.R.T. Hendry, Extending cycles in graphs, Discrete Math. 85 (1990) 59–72. doi:10.1016/0012-365X(90)90163-C

[9] D.J. Oberly and D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory 3 (1979) 351–356. doi:10.1002/jgt.3190030405

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

[11] C.M. Pareek and Z. Skupień, On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait Sci. 10 (1983) 9–16.

[12] Z. Skupień, On the locally Hamiltonian graphs and Kuratowski’s theorem, Bull. Acad. Pol. Sci., Ser. Sci. Math. Astron. Phys. 13 (1965) 615–619.

[13] Z. Skupień, Locally Hamiltonian and planar graphs, Fund. Math. 58 (1966) 193–200. doi:10.4064/fm-58-2-193-200

[14] 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. doi:10.1016/j.dam.2015.09.022

[15] D.B. West, Research problems, Discrete Math. 272 (2003) 301–306. doi:10.1016/S0012-365X(03)00207-3