A note on collapsible graphs and super-Eulerian graphs

详细信息    查看全文

• 作者：Hao Li ; Weihua Yang ; ^{ywh222@163.com}
• 关键词：Line graph ; Super-Eulerian graph ; Collapsible graph ; Eulerian trail ; Hamiltonian line graph
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：6 August, 2012
• 年：2012
• 卷：312
• 期：15
• 页码：2223-2227
• 全文大小：204 K

文摘

A graph is called super-Eulerian if it has a spanning closed trail. Let be a graph with vertices. Catlin in (1987)? proved that if for each edge , then has a spanning trail except for several defined graphs. In this work we prove that if for each edge , then is collapsible except for several special graphs, which strengthens the result of Catlin¡¯s, where for even and for odd. As corollaries, a characterization for graphs satisfying for each edge to be super-Eulerian is obtained; by using a theorem of Harary and Nash-Williams, the works here also imply the previous results in? by Brualdi and Shanny (1981), and in? by Clark (1984).