The New Lower Bound of the Number of Vertices of Degree 5 in Contraction Critical 5-Connected Graphs

Springer Science and Business Media LLC - Tập 26 - Trang 395-406 - 2010
Tingting Li1, Jianji Su2
1Department of Public Teaching, Guangxi Economic Management Cadre College, Nanning, People’s Republic of China
2Department of Mathematics, Guangxi Normal University, Guilin, People’s Republic of China

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)