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 -