| Title:
|
Contractible edges in some $k$-connected graphs (English) |
| Author:
|
Yang, Yingqiu |
| Author:
|
Sun, Liang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
62 |
| Issue:
|
3 |
| Year:
|
2012 |
| Pages:
|
637-644 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
component |
| Keyword:
|
contractible edge |
| Keyword:
|
$k$-connected graph |
| Keyword:
|
minimally $k$-connected graph |
| MSC:
|
05C40 |
| MSC:
|
05C76 |
| idZBL:
|
Zbl 1265.05339 |
| idMR:
|
MR2984624 |
| DOI:
|
10.1007/s10587-012-0055-0 |
| . |
| Date available:
|
2012-11-10T21:01:55Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143015 |
| . |
| Reference:
|
[1] Ando, K., Kaneko, A., Kawarabayashi, K.: Contractible edges in minimally $k$-connected graphs.Discrete Math. 308 (2008), 597-602. Zbl 1130.05032, MR 2376482, 10.1016/j.disc.2007.03.025 |
| Reference:
|
[2] Ando, K., Kaneko, A., Kawarabayashi, K., Yoshiomoto, K.: Contractible edges and bowties in a $k$-connected graph.Ars Combin. 64 (2002), 239-247. Zbl 1071.05543, MR 1914212 |
| Reference:
|
[3] Egawa, Y., Enomoto, H., Saito, A.: Contractible edges in triangle-free graphs.Combinatorica 6 (1986), 269-274. Zbl 0607.05046, MR 0875294, 10.1007/BF02579387 |
| Reference:
|
[4] Halin, R.: A theorem on $n$-connected graphs.J. Combin. Theory 7 (1969), 150-154. Zbl 0172.25803, MR 0248042, 10.1016/S0021-9800(69)80049-9 |
| Reference:
|
[5] Kawarabayashi, K.: Note on $k$-contractible edges in $k$-connected graphs.Australasian J. Combin. 24 (2001), 165-168. Zbl 0982.05061, MR 1852817 |
| Reference:
|
[6] Kawarabayashi, K.: Contractible edges and triangles in $k$-connected graphs.J. Combin. Theory, Ser. B 85 (2002), 207-221. Zbl 1031.05076, MR 1912964, 10.1006/jctb.2001.2096 |
| Reference:
|
[7] Mader, W.: Ecken vom Grad $n$ in minimalen $n$-fach zusammenhängenden Graphen.Archiv der Mathematik 23 (1972), 219-224 German. Zbl 0212.29402, MR 0306043, 10.1007/BF01304873 |
| Reference:
|
[8] Mader, W.: Disjunkte Fragmente in kritisch $n$-fach zusammenhängende Graphen.European J. Combin. 6 (1985), 353-359 German. MR 0829354, 10.1016/S0195-6698(85)80048-2 |
| Reference:
|
[9] Mader, W.: Generalizations of critical connectivity of graphs.Discrete Math. 72 (1988), 267-283. MR 0975546, 10.1016/0012-365X(88)90216-6 |
| Reference:
|
[10] Thomassen, C.: Non-separating cycles in $k$-connected graphs.J. Graph Theory 5 (1981), 351-354. MR 0635696, 10.1002/jgt.3190050403 |
| . |
