✦ LIBER ✦

Supereulerian Graphs and the Petersen Graph

✍ Scribed by Paul A. Catlin; Hong-Jian Lai

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 619 KB
Volume: 66
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0009

No coin nor oath required. For personal study only.

✦ Synopsis

Any 3-edge-connected graph with at most 10 edge cuts of size 3 either has a spanning closed trail or it is contractible to the Petersen graph.

📜 SIMILAR VOLUMES

Supereulerian complementary graphs

✍ Hong-Jian Lai 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 541 KB

## Abstract Nebeský in [12] show that for any simple graph with __n__ ≥ 5 vertices, either __G__ or __G^c^__ contains an eulerian subgraph with order at least __n__ ‐ 1, with an explicitly described class of exceptional graphs. In this note, we show that if __G__ is a simple graph with __n__ ≥ 61 v

Supereulerian graphs: A survey

✍ Paul A. Catlin 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 996 KB

## Abstract A graph is __supereulerian__ if it has a spanning eulerian subgraph. There is a rduction method to determine whether a graph is supereulerian, and it can also be applied to study other concepts, e.g., hamiltonian line graphs, a certain type of double cycle cover, and the total interval

Supereulerian graphs and excluded induce

Supereulerian graphs and excluded induced minors

✍ Hong-Jian Lai 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 494 KB

We show that if a graph G with r'(G) 1> 2 does not have an induced subgraph contractible to K2, 3 or to one of the subdivided wheels, then G has a spanning eulerian subgraph. As a corollary, such a graph has a nowhere-zero 4-flow.

The ubiquitous Petersen graph

✍ Gary Chartrand; Héctor Hevia; Robin J. Wilson 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 507 KB

Locally petersen graphs

✍ J. I. Hall 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 684 KB

## Abstract A graph Γ is locally Petersen if, for each point __t__ of Γ, the graph induced by Γ on all points adjacent to __t__ is isomorphic to the Petersen graph. We prove that there are exactly three isomorphism classes of connected, locally Petersen graphs and further characterize these graphs

A reduction criterion for supereulerian

A reduction criterion for supereulerian graphs

✍ Catlin, Paul A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

Let G be a graph, and let H be a connected subgraph of G. When it is known that the graph G/H (obtained from G by contracting H to a vertex) has a spanning eulerian subgraph, under what conditions can it be inferred that G itself has a spanning eulerian subgraph? 0 1996 John Wiley & Sons, Inc.