抄録
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.
| 本文言語 | English |
|---|---|
| ページ（範囲） | 333-354 |
| ページ数 | 22 |
| ジャーナル | Graphs and Combinatorics |
| 巻 | 4 |
| 号 | 1 |
| DOI | |
| 出版ステータス | Published - 1988 12月 1 |
| 外部発表 | はい |
ASJC Scopus subject areas
- 理論的コンピュータサイエンス
- 離散数学と組合せ数学