You're viewing this item in the new Europeana website. View this item in the original Europeana.

Contractible edges in some $k$-connected graphs

An edge $e$ of a $k$-connected graph $G$ is said to be $k$-contractible (or simply contractible) if the graph obtained from $G$ by contracting $e$ (i.e., deleting $e$ and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still $k$-connected. In 2002, Kawarabayashi proved that for any odd integer $k\geq 5$, if $G$ is a $k$-connected graph and …