Abstract | ||
---|---|---|
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). |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.dam.2015.07.013 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Supereulerian graphs,Collapsible graphs,Edge-connectivity,Edge-disjoint trails,Supereulerian graphs with width s,The supereulerian width of a graph,s-collapsible graphs,Eulerian-connected graphs | Integer,Discrete mathematics,Graph,Indifference graph,Combinatorics,Chordal graph,Eulerian path,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | ISSN | Citations |
200 | 0166-218X | 2 |
PageRank | References | Authors |
0.40 | 14 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ping Li | 1 | 21 | 7.14 |
Hao Li | 2 | 5 | 2.52 |
Ye Chen | 3 | 66 | 7.20 |
Herbert Fleischner | 4 | 224 | 35.35 |
Hong-Jian Lai | 5 | 631 | 97.39 |