[Back]

P. Li, H. Li, Y. Chen, H. Fleischner, H. Lai:
"Supereulerian graphs with width s and s-collapsible graphs";
Discrete Applied Mathematics, 200 (2016), 79 - 94.

For an integer s>0s>0 and for u,v∈V(G)u,v∈V(G) with u≠vu≠v, an (s;u,v)(s;u,v)-trail-system of GG is a subgraph HH consisting of ss edge-disjoint (u,v)(u,v)-trails. A graph is supereulerian with widthss if for any u,v∈V(G)u,v∈V(G) with u≠vu≠v, GG has a spanning (s;u,v)(s;u,v)-trail-system. The supereulerian widthμ′(G)μ′(G) of a graph GG is the largest integer ss such that GG is supereulerian with width kk for every integer kk with 0≤k≤s0≤k≤s. Thus a graph GG with μ′(G)≥2μ′(G)≥2 has a spanning Eulerian subgraph. Catlin (1988) introduced collapsible graphs to study graphs with spanning Eulerian subgraphs, and showed that every collapsible graph GG satisfies μ′(G)≥2μ′(G)≥2 (Catlin, 1988; Lai et al., 2009). Graphs GG with μ′(G)≥2μ′(G)≥2 have also been investigated by Luo et al. (2006) as Eulerian-connected graphs. In this paper, we extend collapsible graphs to ss-collapsible graphs and develop a new related reduction method to study μ′(G)μ′(G) for a graph GG. In particular, we prove that K3,3K3,3 is the smallest 3-edge-connected graph with μ′<3μ′<3. These results and the reduction method will be applied to determine a best possible degree condition for graphs with supereulerian width at least 3, which extends former results in Catlin (1988) and Lai (1988).

http://dx.doi.org/10.1016/j.dam.2015.07.013

http://publik.tuwien.ac.at/files/PubDat_252223.pdf