Research ArticleOpen AccessGoogle Scholar indexed
Supereulerian Indices of Some Classes of Graphs
Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
- 1 Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
- 2 Department of Mathematics and Statistics, Qinghai Minzu University, Xining, China
Applied Mathematics·Volume 16 (2025)·Pages 357–364·Published 11 April 2025·DOI10.4236/am.2025.164019
Copy link · social · email
Abstract
Researching Supereulerian index of a graph G is NP-hard. In this paper, we consider Supereulerian indices of some classes of graphs, Supereulerian index means the minimum integer k of iterated line graph L k ( G ) of a graph G such that L k ( G ) is Supereulerian. We show that Supereulerian indices of those graphs obtained by replacing every vertex of Petersen graph with n -cycle or a complete graph of order n , or adding n pendant edges to each vertex of Petersen graph are both 1. Concurrently, we show that Supereulerian indices of partial Generalized Petersen graphs are also 1.
KeywordsPetersen GraphGeneralized Petersen GraphSupereulerian IndexIterated Line Graph
- Bondy, J.A. and Murty U.S.R. (1976) Graph Theory with Applications. Elsevier.
- Watkins, M.E. (1969) A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs. Journal of Combinatorial Theory , 6, 152-164. https://doi.org/10.1016/s0021-9800(69)80116-x
- Frucht, R. (1977) A Canonical Representation of Trivalent Hamiltonian Graphs. Journal of Graph Theory , 1, 45-60. https://doi.org/10.1002/jgt.3190010111
- Alspach, B. (1983) The Classification of Hamiltonian Generalized Petersen Graphs. Journal of Combinatorial Theory , Series B , 34, 293-312. https://doi.org/10.1016/0095-8956(83)90042-4
- Chartrand, G. (1968) On Hamiltonian Line-Graphs. Transactions of the American Mathematical Society , 134, 559-566. https://doi.org/10.1090/s0002-9947-1968-0231740-1
- Chartrand, G. and Wall, C.E. (1973) On the Hamiltonian Index of a Graph. Studia Scientiarum Mathematicarum Hungarica , 8, 43-48.
- Chark, L.H. and Wormald, N.C. (1983) Hamiltonian-Like Indices of Graphs. Ars Combinatoria , 15, 131-148.
- Catlin, P.A., Janakiraman, I.T.N. and Srinivasan, N. (1990) Hamilton Cycles and Closed Trails in Iterated Line Graphs. Journal of Graph Theory , 14, 347-364. https://doi.org/10.1002/jgt.3190140308
- Han, L., Lai, H., Xiong, L. and Yan, H. (2010) The Chvátal-Erdös Condition for Supereulerian Graphs and the Hamiltonian Index. Discrete Mathematics , 310, 2082-2090. https://doi.org/10.1016/j.disc.2010.03.020
- Xiong, L.M. and Yan, H.Y. (2005) On the Supereulerian Index of a Graph. Journal of Beijing Institute of Technology , 14, 453-457.
- Xiong, L.M. and Li, M.C. (2010) Supereulerian Index Is Stable under Contractions and Closures. Ars Combinatoria , 97, 129-142.
- Xiong, L.M., Liu Z.M. and Yi, G.S. (2000) Characterization of the n -th Supereulerian Iterated Line Graph. Journal of Jiangxi Normal University , No. 24, 107-110.