Graphs G for which both G and G¯ are Contraction Critically k-Connected |
| |
| Authors: | Jin Akiyama Kiyoshi Ando Yoshimi Egawa |
| |
| Affiliation: | (1) Research Institute of Educational Development, Tokai University, 2–28–4 Tomigaya, Shibuya-ku, Tokyo 151–0063, Japan, JP;(2) Department of Information and Communication Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182–8585, Japan, JP;(3) Department of Mathematical Information Science, Science University of Tokyo, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162–8601, Japan, JP |
| |
| Abstract: | An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k 5/3+4k 3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40 |
| |
| Keywords: | . k-Connected graph, Contractible edge, Contraction critically k-connected, Complement |
| 本文献已被 SpringerLink 等数据库收录！ |
|
