Conditions for $k$-connected graphs to have a $k$-contractible edge

Kiyoshi Ando
Natinal Institute of Informatics, JST ERATO Kawarabayashi Large Graph Project



Content: An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of it results a $k$-connected graph. When $k\le 3$, each $k$-connected graph on more then $k+1$ vertices has a $k$-contractible edge. When $k\ge 4$, there are infinitely many $k$-connected graphs with no $k$-contractible edge. Hence, if $k\ge 4$, we can not expect the existence of a $k$-contractible edge in a $k$-connected graph with no condition. We say `$k$-sufficient condition' for a condition for a $k$-connected graph to have a $k$-contractible edge. In this talk, we give some $k$-sufficient conditions involving forbidden subgraphs, one of which is an extension of a Kawarabayashi's result.

Back to all abstracts