Supereulerian Index is Stable Under Contractions and Closures

Abstract

The supereulerian index of a graph $G$ is the smallest integer $k$ such that the $k$-th iterated line graph of $G$ is supereulerian. We first show that adding an edge between two vertices with degree sums at least three in a graph cannot increase its supereulerian index. We use this result to prove that the supereulerian index of a graph $G$ will not be changed after either of contracting an $A_G(F)$-contractible subgraph $F$ of a graph $G$ and performing the closure operation on $G$ (if $G$ is claw-free). Our results extend Catlin’s remarkable theorem $[4]$ relating that the supereulericity of a graph is stable under the contraction of a collapsible subgraph.