Opuscula Mathematica
Opuscula Math. 45, no. 2 (2025), 275-285

Local properties of graphs that induce global cycle properties

Yanyan Wang
Xiaojing Yang
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.
Full text (pdf)
References ▼
  1. [1] 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
  2. [2] 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
  3. [3] 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
  4. [4] 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
  5. [5] 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
  6. [6] G.R.T. Hendry, A strengthening of Kikustapos;s theorem, J. Graph Theory 13 (1989) 257-260. https://doi.org/10.1002/jgt.3190130212
  7. [7] G.R.T. Hendry, Extending cycles in graphs, Discrete Math. 85 (1990), 59-72. https://doi.org/10.1016/0012-365x(90)90163-c
  8. [8] P.A. Irzhavski, Hamiltonicity of locally connected graphs: complexity results, Vestsi NAN Belarusi. Ser, Fiz-Mat. Navuk. 4 (2014), 37-43 [in Russian].
  9. [9] 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
  10. [10] Z. Skupień, Locally Hamiltonian graphs and Kuratowski theorem, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 13 (1965), 615-619.
  11. [11] 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
  12. [12] D. West, Research problems, Discrete Math. 272 (2003), 301-306. https://doi.org/10.1016/s0012-365x(03)00207-3
  13. [13] 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
About the authors ▼
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
About the article ▼
Communicated by Mirko Horňák.
Received: 2024-07-20.
Revised: 2025-01-22.
Accepted: 2025-01-22.
Published online: 2025-03-10.
Cite this article as ▼
Yanyan Wang, Xiaojing Yang, Local properties of graphs that induce global cycle properties, Opuscula Math. 45, no. 2 (2025), 275-285, https://doi.org/10.7494/OpMath.2025.45.2.275.
Download this article's citation as: