Abstract
An edge of a 3-connected graph is called contractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has ⌈|G|/2⌉ or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphs G have more than ⌈|G|/2⌉ contractible edges.
| Original language | English |
|---|---|
| Pages (from-to) | 333-354 |
| Number of pages | 22 |
| Journal | Graphs and Combinatorics |
| Volume | 4 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1988 Dec 1 |
| Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics