Supereulerian graphs with width s and s-collapsible graphs

Ping Li, Hao Li, Ye Chen, Herbert Fleischner, Hong Jian Lai

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish (US)
Pages (from-to)79-94
Number of pages16
JournalDiscrete Applied Mathematics
Volume200
DOIs
StatePublished - Feb 19 2016
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Supereulerian graphs with width s and s-collapsible graphs'. Together they form a unique fingerprint.

Cite this