Degree Sum And Collapsible Graphs

For a graph G, let O(G) denote the set of odd degree vertices of G. A graph G is collapsible if for any subset R C V(G) with|R|=0(mod2), G has a spanning connected subgraph HR such that O(HR)=R. Let G be a graph on n≥8vertices. In this paper, we prove that if d(x)+d(y)≥n-2-p(n) for each xy∈E(G), then G is collapsible or G is one of several special graphs, where p(n)=0for n even and p(n)=1for n odd, which generalizes the earlier results by Catlin [J. Graph Theory,11(1987)161-167], and by Li and Yang [Discrete Math.,312(2012)2223-2227]. Besides, the works here also get the the result similar to the previous result in [19] by Brualdi and Shanny (1981) and in [20] by Clark (1984) by using a result of Harary and Nash-Williams.