Geodesic
Contractible edges in some $k$-connected graphs
Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 637-644

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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 $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\geq 3$ and any odd integer $k \geq 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.
DOI : 10.1007/s10587-012-0055-0
Classification : 05C40, 05C76
Keywords: component; contractible edge; $k$-connected graph; minimally $k$-connected graph 
@article{10_1007_s10587_012_0055_0,
     author = {Yang, Yingqiu and Sun, Liang},
     title = {Contractible edges in some $k$-connected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {637--644},
     publisher = {mathdoc},
     volume = {62},
     number = {3},
     year = {2012},
     doi = {10.1007/s10587-012-0055-0},
     mrnumber = {2984624},
     zbl = {1265.05339},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0055-0/}
}
TY  - JOUR
AU  - Yang, Yingqiu
AU  - Sun, Liang
TI  - Contractible edges in some $k$-connected graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2012
SP  - 637
EP  - 644
VL  - 62
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0055-0/
DO  - 10.1007/s10587-012-0055-0
LA  - en
ID  - 10_1007_s10587_012_0055_0
ER  - 
%0 Journal Article
%A Yang, Yingqiu
%A Sun, Liang
%T Contractible edges in some $k$-connected graphs
%J Czechoslovak Mathematical Journal
%D 2012
%P 637-644
%V 62
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0055-0/
%R 10.1007/s10587-012-0055-0
%G en
%F 10_1007_s10587_012_0055_0
Yang, Yingqiu; Sun, Liang. Contractible edges in some $k$-connected graphs. Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 637-644. doi: 10.1007/s10587-012-0055-0

Cité par Sources :