✦ LIBER ✦

The spanning subgraphs of eulerian graphs

✍ Scribed by F. T. Boesch; C. Suffel; R. Tindell

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 312 KB
Volume: 1
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190010115

No coin nor oath required. For personal study only.

✦ Synopsis

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 order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.

📜 SIMILAR VOLUMES

A note on graphs spanned by Eulerian gra

A note on graphs spanned by Eulerian graphs

✍ W. R. Pulleyblank 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

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

Spanning even subgraphs of 3-edge-connec

Spanning even subgraphs of 3-edge-connected graphs

✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

Connected Spanning Subgraphs of 3-Connec

Connected Spanning Subgraphs of 3-Connected Planar Graphs

✍ Hikoe Enomoto; Tadashi Iida; Katsuhiro Ota 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 339 KB

Spanning subgraphs of graphs partitioned

Spanning subgraphs of graphs partitioned into two isomorphic pieces

✍ Anthony Bonato 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

## Abstract A graph has the neighbor‐closed‐co‐neighbor, or ncc property, if for each of its vertices __x__, the subgraph induced by the neighbor set of __x__ is isomorphic to the subgraph induced by the closed non‐neighbor set of __x__. As proved by Bonato and Nowakowski [5], graphs with the ncc p

2-Connected Spanning Subgraphs of Planar

2-Connected Spanning Subgraphs of Planar 3-Connected Graphs

✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.

Eulerian subgraphs in 3-edge-connected g

Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs

✍ Zhi-Hong Chen; Hong-Jian Lai; Xiangwen Li; Deying Li; Jinzhong Mao 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

## Abstract In this paper, we show that if __G__ is a 3‐edge‐connected graph with $S \subseteq V(G)$ and $|S| \le 12$, then either __G__ has an Eulerian subgraph __H__ such that $S \subseteq V(H)$, or __G__ can be contracted to the Petersen graph in such a way that the preimage of each vertex of th