## 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).

Original language | English (US) |
---|---|

Pages (from-to) | 79-94 |

Number of pages | 16 |

Journal | Discrete Applied Mathematics |

Volume | 200 |

DOIs | |

State | Published - Feb 19 2016 |

Externally published | Yes |

## Keywords

- Collapsible graphs
- Edge-connectivity
- Edge-disjoint trails
- Eulerian-connected graphs
- Supereulerian graphs
- Supereulerian graphs with width s
- The supereulerian width of a graph
- s-collapsible graphs

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics