Title: | The contractible subgraph of $5$-connected graphs (English) |

Author: | Qin, Chengfu |

Author: | Guo, Xiaofeng |

Author: | Yang, Weihua |

Language: | English |

Journal: | Czechoslovak Mathematical Journal |

ISSN: | 0011-4642 (print) |

ISSN: | 1572-9141 (online) |

Volume: | 63 |

Issue: | 3 |

Year: | 2013 |

Pages: | 671-677 |

Summary lang: | English |

. | |

Category: | math |

. | |

Summary: | An edge $e$ of a $k$-connected graph $G$ is said to be $k$-removable if $G-e$ is still $k$-connected. A subgraph $H$ of a $k$-connected graph is said to be $k$-contractible if its contraction results still in a $k$-connected graph. A $k$-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally $k$-connected. In this paper, we show that there is a contractible subgraph in a $5$-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally $5$-connected graph is contained in some triangle. (English) |

Keyword: | 5-connected graph |

Keyword: | contractible subgraph |

Keyword: | minor minimally $k$-connected |

MSC: | 05C40 |

MSC: | 05C83 |

idZBL: | Zbl 06282104 |

idMR: | MR3125648 |

DOI: | 10.1007/s10587-013-0046-9 |

. | |

Date available: | 2013-10-07T12:02:26Z |

Last updated: | 2020-07-03 |

Stable URL: | http://hdl.handle.net/10338.dmlcz/143483 |

. | |

Reference: | [1] Ando, K., Qin, C.: Some structural properties of minimally contraction-critically $5$-connected graphs.Discrete Math. 311 (2011), 1084-1097. Zbl 1222.05128, MR 2793219, 10.1016/j.disc.2010.10.022 |

Reference: | [2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.American Elsevier Publishing New York (1976). MR 0411988 |

Reference: | [3] Fijavž, G.: Graph Minors and Connectivity. Ph.D. Thesis.University of Ljubljana (2001). |

Reference: | [4] Kriesell, M.: Triangle density and contractibility.Comb. Probab. Comput. 14 (2005), 133-146. Zbl 1059.05065, MR 2128086, 10.1017/S0963548304006601 |

Reference: | [5] Kriesell, M.: How to contract an essentially $6$-connected graph to a $5$-connected graph.Discrete Math. 307 (2007), 494-510. Zbl 1109.05062, MR 2287490, 10.1016/j.disc.2005.09.040 |

Reference: | [6] Mader, W.: Generalizations of critical connectivity of graphs.Proceedings of the first Japan conference on graph theory and applications. Hakone, Japan, June 1-5, 1986. Discrete Mathematics {\it 72} J. Akiyama, Y. Egawa, H. Enomoto North-Holland Amsterdam (1988), 267-283. MR 0975546, 10.1016/0012-365X(88)90216-6 |

Reference: | [7] Qin, C., Yuan, X., Su, J.: Triangles in contraction critical $5$-connected graphs.Australas. J. Comb. 33 (2005), 139-146. Zbl 1077.05055, MR 2170354 |

Reference: | [8] Tutte, W. T.: A theory of $3$-connected graphs.Nederl. Akad. Wet., Proc., Ser. A 64 (1961), 441-455. Zbl 0101.40903, MR 0140094 |

. |

Files | Size | Format | View |
---|---|---|---|

CzechMathJ_63-2013-3_7.pdf | 236.9Kb | application/pdf |
View/ |