Skip to main navigation Skip to search Skip to main content

Supereulerian index is stable under contractions and closures

  • Liming Xiong*
  • , Mingchu Li
  • *Corresponding author for this work
  • Jiangxi Normal University
  • Dalian University of Technology

Research output: Contribution to journalArticlepeer-review

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 AG(P)-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.

Original languageEnglish
Pages (from-to)129-142
Number of pages14
JournalArs Combinatoria
Volume97
Publication statusPublished - Oct 2010

Keywords

  • Claw-free graph
  • Closure of a graph
  • Collapsible graph
  • Contractible graph
  • Stable property
  • Supereulerian index

Fingerprint

Dive into the research topics of 'Supereulerian index is stable under contractions and closures'. Together they form a unique fingerprint.

Cite this