Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
component; contractible edge; $k$-connected graph; minimally $k$-connected graph
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
Search
Partner of
