Premium
A reduction method to find spanning Eulerian subgraphs
Author(s) -
Catlin Paul A.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120105
Subject(s) - combinatorics , eulerian path , mathematics , graph , graph factorization , degree (music) , set (abstract data type) , reduction (mathematics) , induced subgraph , discrete mathematics , graph power , computer science , line graph , pure mathematics , physics , geometry , lagrangian , acoustics , vertex (graph theory) , programming language
We ask, When does a graph G have a subgraph Γ such that the vertices of odd degree in Γ form a specified set S ⊆ V ( G ), such that G ‐ E (Γ) 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 . We provide a general method, with applications.