A note on collapsible graphs and super-Eulerian graphs

AbstractA graph is called super-Eulerian if it has a spanning closed trail. Let G be a graph with n≥4 vertices. Catlin in (1987) [3] proved that if d(x)+d(y)≥n for each edge xy∈E(G), then G has a spanning trail except for several defined graphs. In this work we prove that if d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G), then G is collapsible except for several special graphs, which strengthens the result of Catlin’s, where p(n)=0 for n even and p(n)=1 for n odd. As corollaries, a characterization for graphs satisfying d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G) to be super-Eulerian is obtained; by using a theorem of Harary and Nash-Williams, the works here also imply the previous results in [2] by Brualdi and Shanny (1981), and in [6] by Clark (1984)