Premium
A note on graphs spanned by Eulerian graphs
Author(s) -
Pulleyblank W. R.
Publication year - 1979
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.3190030316
Subject(s) - eulerian path , combinatorics , mathematics , induced subgraph , graph , degree (music) , cograph , block graph , discrete mathematics , pathwidth , line graph , lagrangian , vertex (graph theory) , physics , acoustics
Abstract We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.