Geodesic
The contractible subgraph of $5$-connected graphs
Czechoslovak Mathematical Journal, Tome 63 (2013) no. 3, pp. 671-677
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-013-0046-9
Classification : 05C40, 05C83
Keywords: 5-connected graph; contractible subgraph; minor minimally $k$-connected 
@article{10_1007_s10587_013_0046_9,
     author = {Qin, Chengfu and Guo, Xiaofeng and Yang, Weihua},
     title = {The contractible subgraph of $5$-connected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {671--677},
     year = {2013},
     volume = {63},
     number = {3},
     doi = {10.1007/s10587-013-0046-9},
     mrnumber = {3125648},
     zbl = {06282104},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0046-9/}
}
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
SP  - 671
EP  - 677
VL  - 63
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0046-9/
DO  - 10.1007/s10587-013-0046-9
LA  - en
ID  - 10_1007_s10587_013_0046_9
ER  - 
%0 Journal Article
%A Qin, Chengfu
%A Guo, Xiaofeng
%A Yang, Weihua
%T The contractible subgraph of $5$-connected graphs
%J Czechoslovak Mathematical Journal
%D 2013
%P 671-677
%V 63
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-013-0046-9/
%R 10.1007/s10587-013-0046-9
%G en
%F 10_1007_s10587_013_0046_9
Qin, Chengfu; Guo, Xiaofeng; Yang, Weihua. The contractible subgraph of $5$-connected graphs. Czechoslovak Mathematical Journal, Tome 63 (2013) no. 3, pp. 671-677. doi: 10.1007/s10587-013-0046-9

[1] Ando, K., Qin, C.: Some structural properties of minimally contraction-critically $5$-connected graphs. Discrete Math. 311 (2011), 1084-1097. | DOI | MR | Zbl

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

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

[4] Kriesell, M.: Triangle density and contractibility. Comb. Probab. Comput. 14 (2005), 133-146. | DOI | MR | Zbl

[5] Kriesell, M.: How to contract an essentially $6$-connected graph to a $5$-connected graph. Discrete Math. 307 (2007), 494-510. | DOI | MR | Zbl

[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. | DOI | MR

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

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

Cité par Sources :