# Article

Full entry | PDF   (0.1 MB)
Keywords:
component; contractible edge; \$k\$-connected graph; minimally \$k\$-connected graph
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.
References:
[1] Ando, K., Kaneko, A., Kawarabayashi, K.: Contractible edges in minimally \$k\$-connected graphs. Discrete Math. 308 (2008), 597-602. DOI 10.1016/j.disc.2007.03.025 | MR 2376482 | Zbl 1130.05032
[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 1914212 | Zbl 1071.05543
[3] Egawa, Y., Enomoto, H., Saito, A.: Contractible edges in triangle-free graphs. Combinatorica 6 (1986), 269-274. DOI 10.1007/BF02579387 | MR 0875294 | Zbl 0607.05046
[4] Halin, R.: A theorem on \$n\$-connected graphs. J. Combin. Theory 7 (1969), 150-154. DOI 10.1016/S0021-9800(69)80049-9 | MR 0248042 | Zbl 0172.25803
[5] Kawarabayashi, K.: Note on \$k\$-contractible edges in \$k\$-connected graphs. Australasian J. Combin. 24 (2001), 165-168. MR 1852817 | Zbl 0982.05061
[6] Kawarabayashi, K.: Contractible edges and triangles in \$k\$-connected graphs. J. Combin. Theory, Ser. B 85 (2002), 207-221. DOI 10.1006/jctb.2001.2096 | MR 1912964 | Zbl 1031.05076
[7] Mader, W.: Ecken vom Grad \$n\$ in minimalen \$n\$-fach zusammenhängenden Graphen. Archiv der Mathematik 23 (1972), 219-224 German. DOI 10.1007/BF01304873 | MR 0306043 | Zbl 0212.29402
[8] Mader, W.: Disjunkte Fragmente in kritisch \$n\$-fach zusammenhängende Graphen. European J. Combin. 6 (1985), 353-359 German. DOI 10.1016/S0195-6698(85)80048-2 | MR 0829354
[9] Mader, W.: Generalizations of critical connectivity of graphs. Discrete Math. 72 (1988), 267-283. DOI 10.1016/0012-365X(88)90216-6 | MR 0975546
[10] Thomassen, C.: Non-separating cycles in \$k\$-connected graphs. J. Graph Theory 5 (1981), 351-354. DOI 10.1002/jgt.3190050403 | MR 0635696

Partner of