“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 r-regular 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 5-regular 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 claw-free graphs having no vertex of degree 4. Indeed, Catlin's conjecture does not hold for claw-free graphs in general.
Download TeX format |
|
| back to top | |
