“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 15368
School of Mathematics
  Title:   Spanning Eulerian subgraphs of large size
  Author(s):  Dariush Kiani
  Status:   To Appear
  Journal: Graphs Combin.
  Supported by:  IPM
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
scroll left or right