In this paper, we mainly considered the Hamilton-connected indices of the Petersen graph and the graphs obtained by replacing each vertices of the Petersen graph with an n-cycle. Hamilton-connected index is the minimum integer m of the m-time iterated line graph Lm(G) of Petersen graph classes such that Lm(G) is Hamilton-connected. A graph G is Hamilton-connected if any two vertices of G are connected by a Hamilton path. We show that the Hamilton-connected indices of the Petersen graphs is 1, and the Hamilton-connected indicies of graphs obtained by replacing each vertex of the Petersen graph with an n-cycle (3≤n≤6) is 2.

Petersen graph;Iterated line graph;Hamilton-connected index

[1] Bondy, J.A.; Murty U.S.R. Graph theory with applications. Macmillan, London and Elsevier, New York, 1976. [2] Harary, F.; Nash-Williams, C.St.J.A. On eulerian and hamiltonian graphs and line graphs. Canad. Math. Bull 1965, 8, 701-709. [3] Chark, L.H.; Wormald, N.C. Hamiltonian-like indices of graphs. ARS Combinatoria 1983, 15, 131-148. [4] Chen, Z.H.; Lai, H.J.; Xiong, L.M.; Yan, H.Y.; Zhan, M.Q. Hamilton-connected indices of graphs. Discrete Math 2009, 309, 4819-4827. [5] Sabir E, Vumar E. Spanning connectivity of the power of a graph and Hamilton- connected index of a graph. Graphs and Combinatorics, 2014,30,1551-1563. [6] Zhan S M. Hamiltonian connectedness of line graphs. Ars Combinatoria, 1986,22: 89-95. [7] S.Zhan, On Hamiltonian line graphs and connectivity. Discrete Math, 1991,158,89-95. [8] Kriesell M. All 4-connected line graphs of claw free graphs are Hamiltonian con- nected. Journal of Combinatorial Theory, Series B, 2001, 82(2): 306-315. [9] Yang W, Lai H, Li H, et al. Collapsible graphs and Hamiltonian connectedness of line graphs. Discrete Applied Mathematics, 2012, 160(12): 1837-1844. [10] Lv S, Zhao L. Hamiltonian Indices of Three Classes of Graphs Obtained from Petersen Graph. Axioms,2023,12(6).

DOI： https://doi.org/10.62639/sspjiss01.20250203

Published： 2025