The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs
Tóm tắt
An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least
$${\frac{1}{2}|G|}$$
vertices of degree 5.
Tài liệu tham khảo
Ando K., Kawarabayashi K., Kaneko A.: Vertices of degree 5 in a contraction critically 5-connected graphs. Graphs Combin. 21, 27–37 (2005)
Bondy J.A., Murty U.S.R.: Graph Theory with Application. Macmillan, New York (1976)
Egawa Y.: Contractible edges in n-connected graphs with minimum degree greater than or equal to \({[\frac{5n}{4}]}\). Graphs Combin. 7(1), 15–21 (1991)
Kriesell M.: A degree sum condition for the existence of a contractible edge in a k-connected graph. J. Combin. Theory Ser. B 82, 81–101 (2001)
Mader W.: Generalizations of critical connectivity of graphs. Discrete Math. 72, 267–283 (1988)
Martinov N.: Uncontractable 4-connected graphs. J. Graph Theory 6, 343–344 (1982)
Qin C., Yuan X., Su J.: Some properties of contraction-critical 5-connected graphs. Discrete Math. 308, 5742–5756 (2008)
Su, J.: The vertices of degree 5 in contraction critical 5-connected graph. J. Guangxi Normal University 3, 12–16 (1997). (in Chinese)
Thomassen C.: Nonseparating cycles in k-connected graphs. J. Graph Theory 5, 351–354 (1981)
Tutte W.T.: A theory of 3-connected graphs. Nederl. Akad. Wet. Proc. Ser. A 64, 441–455 (1961)
Yuan, X.: The contractible edges of 5-connected graphs. J. Guangxi Normal University 3, 30–32 (1994). (in Chinese)