TY - JOUR

T1 - Supereulerian graphs with width s and s-collapsible graphs

AU - Li, Ping

AU - Li, Hao

AU - Chen, Ye

AU - Fleischner, Herbert

AU - Lai, Hong Jian

N1 - Funding Information:
The research of Ping Li is partially supported by National Natural Science Foundation of China ( 11301023 ) and the Fundamental Research Funds for the Central Universities ( 2015JBM105 ). The research of Hao Li is supported in part by the National Natural Science Foundation of China (No. 11301538 ). The research of Herbert Fleischner is supported in part by FWF Project P27615-N25.
Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2016/2/19

Y1 - 2016/2/19

N2 - For an integer s>0 and for u,v∈V(G) with u≠v, an (s;u,v)-trail-system of G is a subgraph H consisting of s edge-disjoint (u,v)-trails. A graph is supereulerian with widths if for any u,v∈V(G) with u≠v, G has a spanning (s;u,v)-trail-system. The supereulerian widthμ′(G) of a graph G is the largest integer s such that G is supereulerian with width k for every integer k with 0≤k≤s. Thus a graph G with μ′(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 G satisfies μ′(G)≥2 (Catlin, 1988; Lai et al., 2009). Graphs G with μ′(G)≥2 have also been investigated by Luo et al. (2006) as Eulerian-connected graphs. In this paper, we extend collapsible graphs to s-collapsible graphs and develop a new related reduction method to study μ′(G) for a graph G. In particular, we prove that K3,3 is the smallest 3-edge-connected graph with μ′<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).

AB - For an integer s>0 and for u,v∈V(G) with u≠v, an (s;u,v)-trail-system of G is a subgraph H consisting of s edge-disjoint (u,v)-trails. A graph is supereulerian with widths if for any u,v∈V(G) with u≠v, G has a spanning (s;u,v)-trail-system. The supereulerian widthμ′(G) of a graph G is the largest integer s such that G is supereulerian with width k for every integer k with 0≤k≤s. Thus a graph G with μ′(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 G satisfies μ′(G)≥2 (Catlin, 1988; Lai et al., 2009). Graphs G with μ′(G)≥2 have also been investigated by Luo et al. (2006) as Eulerian-connected graphs. In this paper, we extend collapsible graphs to s-collapsible graphs and develop a new related reduction method to study μ′(G) for a graph G. In particular, we prove that K3,3 is the smallest 3-edge-connected graph with μ′<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).

KW - Collapsible graphs

KW - Edge-connectivity

KW - Edge-disjoint trails

KW - Eulerian-connected graphs

KW - Supereulerian graphs

KW - Supereulerian graphs with width s

KW - The supereulerian width of a graph

KW - s-collapsible graphs

UR - http://www.scopus.com/inward/record.url?scp=84959317667&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959317667&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2015.07.013

DO - 10.1016/j.dam.2015.07.013

M3 - Article

AN - SCOPUS:84959317667

SN - 0166-218X

VL - 200

SP - 79

EP - 94

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -