Release Time:2019-03-09  Hits:

Indexed by: Journal Article

Date of Publication: 2010-10-01

Journal: ARS COMBINATORIA

Included Journals: Scopus、SCIE

Volume: 97

Page Number: 129-142

ISSN: 0381-7032

Key Words: supereulerian index; stable property; closure of a graph; contractible graph; collapsible graph; claw-free graph

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 a Catlin's remarkable theorem [4] relating that the supereulericity of a graph is stable under the contraction of a collapsible subgraph.