Supereulerian width of dense graphs
2017
For a graph G, the supereulerian width(G) of a graph G is the largest integer s such that G has a spanning (k;u,v)-trail-system, for any integer k with 1ks, and for any u,vV(G) with uv. Thus (G)2 implies that G is supereulerian, and so graphs with higher supereulerian width are natural generalizations of supereulerian graphs. Settling an open problem of Bauer, Catlin (1988) proved that if a simple graph G on n17 vertices satisfy (G)n41, then (G)2. In this paper, we show that for any real numbers a,b with 00, there exists a finite graph family F=F(a,b,s) such that for a simple graph G with n=|V(G)|, if for any u,vV(G) with uvE(G), max{dG(u),dG(v)}an+b, then either (G)s+1 or G is contractible to a member in F. When a=14,b=32, we show that if n is sufficiently large, K3,3 is the only obstacle for a 3-edge-connected graph G to satisfy (G)3.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
1
Citations
NaN
KQI