The number of contractible edges in 3-connected graphs |
| |
Authors: | Katsuhiro Ota |
| |
Affiliation: | (1) Department of Information Science, Faculty of Science, University of Tokyo, Hongo, Bunkyo-ku, 113 Tokyo, Japan |
| |
Abstract: | An edge of a 3-connected graph is calledcontractible 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 graphsG have more than |G|/2 contractible edges. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|