✦ LIBER ✦

A note on graphs spanned by Eulerian graphs

✍ Scribed by W. R. Pulleyblank

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 109 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030316

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A Note on Sub-Eulerian Graphs

✍ F. Jaeger 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract We present an algebraic proof of the following result: a set of edges of a multigraph __G__ is contained in some cycle of __G__ iff the set contains no odd cocycle of __G__ (“cycle” means here: edge disjoint sum of elementary cycles). As a corollary we obtain the characterization of sub

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 note on graphs with diameter-preservin

A note on graphs with diameter-preserving spanning trees

✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using