𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On finding spanning eulerian subgraphs

✍ Scribed by M. B. Richey; R. Gary Parker; R. L. Rardin

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
649 KB
Volume
32
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

πŸ“œ 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

The spanning subgraphs of eulerian graph
The spanning subgraphs of eulerian graphs
✍ F. T. Boesch; C. Suffel; R. Tindell πŸ“‚ Article πŸ“… 1977 πŸ› John Wiley and Sons 🌐 English βš– 312 KB

## Abstract It is shown that a connected graph __G__ spans an eulerian graph if and only if __G__ is not spanned by an odd complete bigraph __K__(2~m~ + 1, 2__n__ + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd

A degree condition for spanning eulerian
A degree condition for spanning eulerian subgraphs
✍ Zhi-Hong Chen πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 571 KB

## 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 l

Finding 2-edge connected spanning subgra
Finding 2-edge connected spanning subgraphs
✍ Woonghee Tim Huh πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 185 KB

This paper studies the NP-hard problem of ΓΏnding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G =(V; E) ΓΏnds a 2-ECSS of size at most |V |+(|E|-|V |)=(r -1). For r-regular, r-edge connected input graphs for r = 3, 4, 5 and