摘要

A graph is called super-Eulerian jut 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 is an element of 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 is an element of 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 is an element of 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).

  • 出版日期2012-8-6