TITLE:
Supereulerian Indices of Some Classes of Graphs
AUTHORS:
Shengmei Lv, Ziyu An
KEYWORDS:
Petersen Graph, Generalized Petersen Graph, Supereulerian Index, Iterated Line Graph
JOURNAL NAME:
Applied Mathematics,
Vol.16 No.4,
April
27,
2025
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.