Contractible edges in some k -connected graphs

Yingqiu Yang; Liang Sun

Czechoslovak Mathematical Journal (2012)

  • Volume: 62, Issue: 3, page 637-644
  • ISSN: 0011-4642

Abstract

top
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 ≥ 5 , if G is a k -connected graph and G contains no subgraph D = K 1 + ( K 2 ∪ K 1 , 2 ) , then G has a k -contractible edge. In this paper, by generalizing this result, we prove that for any integer t ≥ 3 and any odd integer k ≥ 2 t + 1 , if a k -connected graph G contains neither K 1 + ( K 2 ∪ K 1 , t ) , nor K 1 + ( 2 K 2 ∪ K 1 , 2 ) , then G has a k -contractible edge.

How to cite

top

Yang, Yingqiu, and Sun, Liang. "Contractible edges in some $k$-connected graphs." Czechoslovak Mathematical Journal 62.3 (2012): 637-644. <http://eudml.org/doc/246243>.

@article{Yang2012,
abstract = {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\ge 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\ge 3$ and any odd integer $k \ge 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.},
author = {Yang, Yingqiu, Sun, Liang},
journal = {Czechoslovak Mathematical Journal},
keywords = {component; contractible edge; $k$-connected graph; minimally $k$-connected graph; -connected graph; contractible edges; forbidden subgraph; edge contraction},
language = {eng},
number = {3},
pages = {637-644},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Contractible edges in some $k$-connected graphs},
url = {http://eudml.org/doc/246243},
volume = {62},
year = {2012},
}

TY - JOUR
AU - Yang, Yingqiu
AU - Sun, Liang
TI - Contractible edges in some $k$-connected graphs
JO - Czechoslovak Mathematical Journal
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 3
SP - 637
EP - 644
AB - 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\ge 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\ge 3$ and any odd integer $k \ge 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.
LA - eng
KW - component; contractible edge; $k$-connected graph; minimally $k$-connected graph; -connected graph; contractible edges; forbidden subgraph; edge contraction
UR - http://eudml.org/doc/246243
ER -

References

top
  1. Ando, K., Kaneko, A., Kawarabayashi, K., 10.1016/j.disc.2007.03.025, Discrete Math. 308 (2008), 597-602. (2008) Zbl1130.05032MR2376482DOI10.1016/j.disc.2007.03.025
  2. Ando, K., Kaneko, A., Kawarabayashi, K., Yoshiomoto, K., Contractible edges and bowties in a k -connected graph, Ars Combin. 64 (2002), 239-247. (2002) Zbl1071.05543MR1914212
  3. Egawa, Y., Enomoto, H., Saito, A., 10.1007/BF02579387, Combinatorica 6 (1986), 269-274. (1986) Zbl0607.05046MR0875294DOI10.1007/BF02579387
  4. Halin, R., 10.1016/S0021-9800(69)80049-9, J. Combin. Theory 7 (1969), 150-154. (1969) Zbl0172.25803MR0248042DOI10.1016/S0021-9800(69)80049-9
  5. Kawarabayashi, K., Note on k -contractible edges in k -connected graphs, Australasian J. Combin. 24 (2001), 165-168. (2001) Zbl0982.05061MR1852817
  6. Kawarabayashi, K., 10.1006/jctb.2001.2096, J. Combin. Theory, Ser. B 85 (2002), 207-221. (2002) Zbl1031.05076MR1912964DOI10.1006/jctb.2001.2096
  7. Mader, W., 10.1007/BF01304873, Archiv der Mathematik 23 (1972), 219-224 German. (1972) Zbl0212.29402MR0306043DOI10.1007/BF01304873
  8. Mader, W., 10.1016/S0195-6698(85)80048-2, European J. Combin. 6 (1985), 353-359 German. (1985) MR0829354DOI10.1016/S0195-6698(85)80048-2
  9. Mader, W., 10.1016/0012-365X(88)90216-6, Discrete Math. 72 (1988), 267-283. (1988) MR0975546DOI10.1016/0012-365X(88)90216-6
  10. Thomassen, C., 10.1002/jgt.3190050403, J. Graph Theory 5 (1981), 351-354. (1981) MR0635696DOI10.1002/jgt.3190050403

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.