Contractible edges in some $k$-connected graphs

Yang, Yingqiu ; Sun, Liang

Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 637-644.

Résumé

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\ge 5$, if $G$ is a $k$-connected graph and $G$ contains no subgraph $D=K_1+(K_2\cup K_{1,2})$, then $G$ has a $k$-contractible edge. In this paper, by generalizing this result, we prove that for any integer $t\ge 3$ and any odd integer $k\ge 2t+1$, if a $k$-connected graph $G$ contains neither $K_1+(K_2\cup K_{1,t})$, nor $K_1+(2K_2\cup K_{1,2})$, then $G$ has a $k$-contractible edge.

Détail

DOI : 10.1007/s10587-012-0055-0

Classification : 05C40, 05C76
Mots-clés : component; contractible edge; $k$-connected graph; minimally $k$-connected graph