2016/01/07 by Weiguo Chen, Chen, Wei-Guo, Zhi‐Hong Chen +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1601.01365
openalex publication_date 2016/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called collapsible if for every even subset R⊆ V(G), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is the reduction of G if it is obtained from G by contracting all the nontrivial collapsible subgraphs. A graph is reduced if it has no nontrivial collapsible subgraphs. In this paper, we first prove a few results on the properties of reduced graphs. As an application, for 3-edge-connected graphs G of order n with d(u)+d(v)≥ 2(n/p-1) for any uv∈ E(G) where p>0 are given, we show how such graphs change if they have no spanning Eulerian subgraphs when p is increased from p=1 to 10 then to 15.