Opuscula Math. 45, no. 2 (2025), 275-285
https://doi.org/10.7494/OpMath.2025.45.2.275
Opuscula Mathematica
Local properties of graphs that induce global cycle properties
Abstract. A graph \(G\) is locally Hamiltonian if \(G[N(v)]\) is Hamiltonian for every vertex \(v\in V(G)\). In this note, we prove that every locally Hamiltonian graph with maximum degree at least \(|V(G)| - 7\) is weakly pancyclic. Moreover, we show that any connected graph \(G\) with \(\Delta(G)\leq 7\) and \(\delta(G[N(v)])\geq 3\) for every \(v\in V (G)\), is fully cycle extendable. These findings improve some known results by Tang and Vumar.
Keywords: fully cycle extendability, weakly pancyclicity, locally connected.
Mathematics Subject Classification: 05C38, 05C45.
- S.A. van Aardt, M. Frick, O.R. Oellermann, J. 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
- A. Adamaszek, M. Adamaszek, M. Mnich, J.M. Schmidt, Lower bounds for locally highly connected graphs, Graphs Combin. 32 (2016), 1641-1650. https://doi.org/10.1007/s00373-016-1686-y
- J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008. https://doi.org/10.1007/978-1-84628-970-5
- C. Brause, D. Rautenbach, I. Schiermeyer, Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability, Discrete Math. 340 (2017), 596-606. https://doi.org/10.1016/j.disc.2016.11.035
- V.S. Gordon, Y.L. Orlovich, C.N. Potts, V.A. Strusevich, Hamiltonian properties of locally connected graphs with bounded vertex degree, Discrete Appl. Math. 159 (2011), 1759-1774. https://doi.org/10.1016/j.dam.2010.10.005
- G.R.T. Hendry, A strengthening of Kikustapos;s theorem, J. Graph Theory 13 (1989) 257-260. https://doi.org/10.1002/jgt.3190130212
- G.R.T. Hendry, Extending cycles in graphs, Discrete Math. 85 (1990), 59-72. https://doi.org/10.1016/0012-365x(90)90163-c
- P.A. Irzhavski, Hamiltonicity of locally connected graphs: complexity results, Vestsi NAN Belarusi. Ser, Fiz-Mat. Navuk. 4 (2014), 37-43 [in Russian].
- D.J. Oberly, D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory 3 (1979), 351-356. https://doi.org/10.1002/jgt.3190030405
- Z. Skupień, Locally Hamiltonian graphs and Kuratowski theorem, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 13 (1965), 615-619.
- L. Tang, E. Vumar, A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs, Discuss. Math. Graph Theory 40 (2020), 77-84. https://doi.org/10.7151/dmgt.2124
- D. West, Research problems, Discrete Math. 272 (2003), 301-306. https://doi.org/10.1016/s0012-365x(03)00207-3
- J.P. de Wet, M. Frick, 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
- Yanyan Wang
- Henan University, School of Mathematics and Statistics, Kaifeng, 475004, P.R. China
- Xiaojing Yang (corresponding author)
- Henan University, School of Mathematics and Statistics, Kaifeng, 475004, P.R. China
- Communicated by Mirko Horňák.
- Received: 2024-07-20.
- Revised: 2025-01-22.
- Accepted: 2025-01-22.
- Published online: 2025-03-10.
