Geodesic
Contractible edges in some $k$-connected graphs
Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 637-644
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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},
     year = {2012},
     volume = {62},
     number = {3},
     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
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
%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

[1] Ando, K., Kaneko, A., Kawarabayashi, K.: Contractible edges in minimally $k$-connected graphs. Discrete Math. 308 (2008), 597-602. | DOI | MR | Zbl

[2] Ando, K., Kaneko, A., Kawarabayashi, K., Yoshiomoto, K.: Contractible edges and bowties in a $k$-connected graph. Ars Combin. 64 (2002), 239-247. | MR | Zbl

[3] Egawa, Y., Enomoto, H., Saito, A.: Contractible edges in triangle-free graphs. Combinatorica 6 (1986), 269-274. | DOI | MR | Zbl

[4] Halin, R.: A theorem on $n$-connected graphs. J. Combin. Theory 7 (1969), 150-154. | DOI | MR | Zbl

[5] Kawarabayashi, K.: Note on $k$-contractible edges in $k$-connected graphs. Australasian J. Combin. 24 (2001), 165-168. | MR | Zbl

[6] Kawarabayashi, K.: Contractible edges and triangles in $k$-connected graphs. J. Combin. Theory, Ser. B 85 (2002), 207-221. | DOI | MR | Zbl

[7] Mader, W.: Ecken vom Grad $n$ in minimalen $n$-fach zusammenhängenden Graphen. Archiv der Mathematik 23 (1972), 219-224 German. | DOI | MR | Zbl

[8] Mader, W.: Disjunkte Fragmente in kritisch $n$-fach zusammenhängende Graphen. European J. Combin. 6 (1985), 353-359 German. | DOI | MR

[9] Mader, W.: Generalizations of critical connectivity of graphs. Discrete Math. 72 (1988), 267-283. | DOI | MR

[10] Thomassen, C.: Non-separating cycles in $k$-connected graphs. J. Graph Theory 5 (1981), 351-354. | DOI | MR

Cité par Sources :