The contractible subgraph of -connected graphs
Chengfu Qin; Xiaofeng Guo; Weihua Yang
Czechoslovak Mathematical Journal (2013)
- Volume: 63, Issue: 3, page 671-677
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topQin, Chengfu, Guo, Xiaofeng, and Yang, Weihua. "The contractible subgraph of $5$-connected graphs." Czechoslovak Mathematical Journal 63.3 (2013): 671-677. <http://eudml.org/doc/260705>.
@article{Qin2013,
abstract = {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.},
author = {Qin, Chengfu, Guo, Xiaofeng, Yang, Weihua},
journal = {Czechoslovak Mathematical Journal},
keywords = {5-connected graph; contractible subgraph; minor minimally $k$-connected; contractible subgraph; minor minimally -connected},
language = {eng},
number = {3},
pages = {671-677},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The contractible subgraph of $5$-connected graphs},
url = {http://eudml.org/doc/260705},
volume = {63},
year = {2013},
}
TY - JOUR
AU - Qin, Chengfu
AU - Guo, Xiaofeng
AU - Yang, Weihua
TI - The contractible subgraph of $5$-connected graphs
JO - Czechoslovak Mathematical Journal
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 63
IS - 3
SP - 671
EP - 677
AB - 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.
LA - eng
KW - 5-connected graph; contractible subgraph; minor minimally $k$-connected; contractible subgraph; minor minimally -connected
UR - http://eudml.org/doc/260705
ER -
References
top- Ando, K., Qin, C., 10.1016/j.disc.2010.10.022, Discrete Math. 311 (2011), 1084-1097. (2011) Zbl1222.05128MR2793219DOI10.1016/j.disc.2010.10.022
- Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing New York (1976). (1976) MR0411988
- Fijavž, G., Graph Minors and Connectivity. Ph.D. Thesis, University of Ljubljana (2001). (2001)
- Kriesell, M., 10.1017/S0963548304006601, Comb. Probab. Comput. 14 (2005), 133-146. (2005) Zbl1059.05065MR2128086DOI10.1017/S0963548304006601
- Kriesell, M., 10.1016/j.disc.2005.09.040, Discrete Math. 307 (2007), 494-510. (2007) Zbl1109.05062MR2287490DOI10.1016/j.disc.2005.09.040
- Mader, W., 10.1016/0012-365X(88)90216-6, Proceedings of the first Japan conference on graph theory and applications. Hakone, Japan, June 1-5, 1986. Discrete Mathematics J. Akiyama, Y. Egawa, H. Enomoto North-Holland Amsterdam (1988), 267-283. (1988) MR0975546DOI10.1016/0012-365X(88)90216-6
- Qin, C., Yuan, X., Su, J., Triangles in contraction critical -connected graphs, Australas. J. Comb. 33 (2005), 139-146. (2005) Zbl1077.05055MR2170354
- Tutte, W. T., A theory of -connected graphs, Nederl. Akad. Wet., Proc., Ser. A 64 (1961), 441-455. (1961) Zbl0101.40903MR0140094
NotesEmbed ?
topYou 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.