کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647836 | 1342380 | 2012 | 5 صفحه PDF | دانلود رایگان |
A graph is called super-Eulerian if it has a spanning closed trail. Let GG be a graph with n≥4n≥4 vertices. Catlin in (1987) [3] proved that if d(x)+d(y)≥nd(x)+d(y)≥n for each edge xy∈E(G)xy∈E(G), then GG has a spanning trail except for several defined graphs. In this work we prove that if d(x)+d(y)≥n−1−p(n)d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G)xy∈E(G), then GG is collapsible except for several special graphs, which strengthens the result of Catlin’s, where p(n)=0p(n)=0 for nn even and p(n)=1p(n)=1 for nn odd. As corollaries, a characterization for graphs satisfying d(x)+d(y)≥n−1−p(n)d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G)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).
Journal: Discrete Mathematics - Volume 312, Issue 15, 6 August 2012, Pages 2223–2227