Contractible edges in triangle-free graphs |
| |
| Authors: | Yoshimi Egawa Hikoe Enomoto Akira Saito |
| |
| Affiliation: | (1) Dept. of Applied Math., Science University of Tokyo, Shinjuku-ku, 162 Tokyo, Japan;(2) Dept. of Information Science Faculty of Science, University of Tokyo, Hongo, Bunkyo-ku, 113 Tokyo, Japan |
| |
| Abstract: | An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k 2-3k or morek-contractible edges. |
| |
| Keywords: | 05 C 40 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
