Local properties of graphs that induce global cycle properties

• Autorzy: Wang Yanyan , Yang Xiaojing

Identyfikatory

DOI

10.7494/OpMath.2025.45.2.275

• Języki publikacji: EN

Abstrakty

EN

A graph G is locally Hamiltonian if G[N(v)] is Hamiltonian for every vertex v ∈ 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 Δ(G) ≤ 7 and δ(G[N(v)]) ≥ 3 for every v ∈ V (G), is fully cycle extendable. These findings improve some known results by Tang and Vumar.

Słowa kluczowe

EN

fully cycle extendability; weakly pancyclicity; locally connected

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 2
• Strony: 275--285
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Wang Yanyan

• Henan University, School of Mathematics and Statistics, Kaifeng, 475004, P.R. China

autor

Yang Xiaojing

• Henan University, School of Mathematics and Statistics, Kaifeng, 475004, P.R. China

Bibliografia

• [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.
• [2] A. Adamaszek, M. Adamaszek, M. Mnich, J.M. Schmidt, Lower bounds for locally highly connected graphs, Graphs Combin. 32 (2016), 1641–1650.
• [3] J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008.
• [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.
• [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.
• [6] G.R.T. Hendry, A strengthening of Kikustapos;s theorem, J. Graph Theory 13 (1989) 257–260.
• [7] G.R.T. Hendry, Extending cycles in graphs, Discrete Math. 85 (1990), 59–72.
• [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] 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.
• [10] Z. Skupień, Locally Hamiltonian graphs and Kuratowski theorem, Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 13 (1965), 615–619.
• [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.
• [12] D. West, Research problems, Discrete Math. 272 (2003), 301–306.
• [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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)