“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 15368  


Abstract:  
A graph G = (V (G),E(G)) is supereulerian if it has a spanning Eulerian subgraph. Let l(G) be the maximum number of edges of spanning Eulerian subgraphs of a graph G. Motivated by a conjecture due to Catlin on supereulerian graphs, it was shown that if G is an rregular supereulerian graph, then
l(G) 2/3  E(G)  when r 5, and l(G) > 3/ 5  E(G)  when
r = 5. In this paper we improve the coefficient and prove that if G is a 5regular supereulerian graph, then l(G) 19/ 30  E(G)  + 4/ 3. For this, we first show that each graph G with maximum degree at most 3 has a matching with at least
2/ 7  E(G)  edges and this bound is sharp. Moreover, we show that Catlin's conjecture holds for clawfree graphs having no vertex of degree 4. Indeed, Catlin's conjecture does not hold for clawfree graphs in general.
Download TeX format 

back to top 