×

The removable edges and the contractible subgraphs of 5-connected graphs. (English) Zbl 1306.05132

Summary: An edge 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, that is, identification every component of \(H\) to a single vertex, results again a \(k\)-connected graph. In this paper, we show that there is either a removable edge or a contractible subgraph in a 5-connected graph which contains an edge with both endvertices have degree more than five. Thus every edge of minor minimal 5-connected graph is incident to at least one vertex of degree 5.

MSC:

05C40 Connectivity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Tutte W.T.: A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64, 441-455 (1961) · Zbl 0101.40903
[2] Plummer M.D., Toft B.: Cyclic coloration of 3-polytopes. J. Graph Theory 11, 507-515 (1987) · Zbl 0655.05030 · doi:10.1002/jgt.3190110407
[3] Kriesell M.: Contractions, cycle double covers, and cyclic colorings in locally connected graphs. J. Comb. Theory Ser. B 96, 881-900 (2006) · Zbl 1107.05052 · doi:10.1016/j.jctb.2006.02.009
[4] Kriesell M.: Average degree and Contractibility. J. Graph Theory 51, 205-224 (2006) · Zbl 1087.05033 · doi:10.1002/jgt.20131
[5] Su, J.: Vertices of degree 5 in contraction critical 5-connected graphs. J. Guangxi Norm. Univ. 3, 12-16 (1997) (in Chinese)
[6] Yuan, X.: The contractible edges of 5-connected graphs. J. Guangxi Norm. Univ. 3, 30-32 (1994) (in Chinese) · Zbl 0997.05054
[7] Ando K.: Vertices of degree 5 in a contraction critically 5-connected graph. Graphs Comb. 21, 27-37 (2005) · Zbl 1060.05059 · doi:10.1007/s00373-004-0591-y
[8] Ando, K.: (2009) A local structure theorem on 5-connected graphs. J. Graph Theory 60, 99-129 · Zbl 1194.05064
[9] Ando K., Iwase T.: The number of vertices of degree 5 in a contraction critically 5-connected graph. Discrete Math. 331, 1925-1939 (2011) · Zbl 1223.05148 · doi:10.1016/j.disc.2011.04.032
[10] Ando K., Qin C.: Some structural properties of minimally contraction critically 5-connected graphs. Discrete Math. 311, 1084-1097 (2011) · Zbl 1222.05128 · doi:10.1016/j.disc.2010.10.022
[11] Li T., Su J.: A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs. Discrete Math. 309, 2870-2876 (2009) · Zbl 1203.05084 · doi:10.1016/j.disc.2008.07.020
[12] Qin C., Yuan X., Su J.: Some properties of contraction critical 5-connected graphs. Discrete Math. 308, 5742-5756 (2008) · Zbl 1189.05089 · doi:10.1016/j.disc.2007.10.041
[13] Qin C., Yuan X., Su J.: Triangles in contraction critical 5-connected graphs. Aust. J. Comb. 33, 139-146 (2005) · Zbl 1077.05055
[14] Kriesell M.: How to contract an essentially 6-connected graph to a 5-connected graph. Discrete Math. 307, 494-510 (2007) · Zbl 1109.05062 · doi:10.1016/j.disc.2005.09.040
[15] Kriesell M.: A survey on contractible edges in graphs of a given vertex connectivity. Graphs Comb. 18, 1-30 (2002) · Zbl 0997.05054 · doi:10.1007/s003730200000
[16] Fijavž, G.: (2001) Graph minors and connectivity. Ph.D. Thesis, University of Ljubljana · Zbl 0101.40903
[17] Bondy, J.A., Murty, U.S.R.: (1976) Graph Theory with Applications, MacMillan, London · Zbl 1226.05083
[18] Mader, W.: Generalizations of critical connectivity of graphs. Discrete Math. 72, 267-283 (1988) · Zbl 0664.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.