Publications in Scientific Journals:

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.

English abstract:
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).

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.