𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A degree condition for spanning eulerian subgraphs

✍ Scribed by Zhi-Hong Chen

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
571 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let p β‰₯ 2 be a fixed integer. Let G be a simple and 2‐edge‐connected graph on n vertices, and let g be the girth of G. If d(u) + d(v) β‰₯ (2/(g βˆ’ 2))((n/p) βˆ’ 4 + g) holds whenever uv βˆ‰ E(G), and if n is sufficiently large compared to p, then either G has a spanning eulerian subgraph or G can be contracted to a graph G~1~ of order at most p without a spanning eulerian subgraph. Furthermore, we characterize the graphs that satisfy the conditions above such that G~1~ has order p and does not have any spanning eulerian subgraph. Β© 1993 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

A reduction method to find spanning Eule
A reduction method to find spanning Eulerian subgraphs
✍ Paul A. Catlin πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 621 KB

We ask, When does a graph G have a subgraph I' such that the vertices of odd degree in form a specified set S C V ( G ) , such that G -E(T) is connected? If such a subgraph can be found for a suitable choice of S, then this can be applied to problems such as finding a spanning eulerian subgraph of G

A 3-Approximation Algorithm for Finding
A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
✍ Yefim Dinitz; Zeev Nutov πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 103 KB

The problem of finding a minimum weight k-vertex connected spanning sub-Ε½ . graph in a graph G s V, E is considered. For k G 2, this problem is known to be NP-hard. Based on the paper of Auletta, Dinitz, Nutov, and Parente in this issue, Γ„ 4 we derive a 3-approximation algorithm for k g 4, 5 . This