• 3
  • 3
  • 82
  • 82
IPM
30
YEARS OLD

“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
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right