The Average Degree of Minimally Contraction‐Critically 5‐Connected Graphs |
| |
| Authors: | Kiyoshi Ando Yoshimi Egawa Matthias Kriesell |
| |
| Affiliation: | 1. DEPARTMENT OF INFORMATICSTHE UNIVERSITY OF ELECTRO‐COMMUNICATIONS;2. DEPARTMENT OF MATHEMATICAL INFORMATION SCIENCETOKYO UNIVERSITY OF SCIENCE;3. DEPARTMENT OF MATHEMATICSILMENAU UNIVERSITY OF TECHNOLOGY |
| |
| Abstract: | An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than  . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than  . |
| |
| Keywords: | 5‐connected graph contraction‐critically 5‐connected degree 5 vertex AMS classification 05C40 |
|
