|
|||||
|
|
Non-contractible edges in a 3-connected graph |
|
| Authors: | Yoshimi Egawa Katsuhiro Ota Akira Saito Xingxing Yu |
| Affiliation: | 1. Department of Applied Mathematics, Science University of Tokyo, Shinjuku-ku, 162, Tokyo, JAPAN 2. Department of Mathematics, Keio University, Hiyoshi 3-14-1, Kohoku-ku, 223, Yokohama-shi, Kanagawa, JAPAN 3. Department of Mathematics, Nihon University, Sakurajosui 3-25-40 Setagaya-ku, 156, Tokyo, JAPAN 4. School of Mathematics, Georgia Institute of Technology, 30332, Atlanta, Georgia, USA |
| Abstract: | An edgee in a 3-connected graphG is contractible if the contraction ofe inG results in a 3-connected graph; otherwisee is non-contractible. In this paper, we prove that the number of non-contractible edges in a 3-connected graph of orderp≥5 is at most $$3p - left[ {frac{3}{2}(sqrt {24p + 25} - 5} right],$$ and show that this upper bound is the best possible for infinitely many values ofp. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |