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 language | English |
|---|---|
| Pages (from-to) | 129-142 |
| Number of pages | 14 |
| Journal | Ars Combinatoria |
| Volume | 97 |
| Publication status | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver