✦ LIBER ✦

Supereulerian complementary graphs

✍ Scribed by Hong-Jian Lai

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 541 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170214

No coin nor oath required. For personal study only.

✦ Synopsis

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 vertices, then either G or G^c^ is supereulerian, with some exceptions. We also characterize all these exceptional cases. These results are applied to show that if G is a simple graph with n ≥ 61 vertices such that both G and G^c^ are connected, then either G or G^c^ has a 4‐flow, or both G and G^c^ have cut‐edges. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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 the Petersen Gr

Supereulerian Graphs and the Petersen Graph

✍ Paul A. Catlin; Hong-Jian Lai 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 619 KB

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.

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.

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.

Self-complementary graphs

✍ Richard A Gibbs 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 762 KB

Self-complementary symmetric graphs

✍ Hong Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 236 KB

## Abstract The class of self‐complementary symmetric graphs is characterized using the classification of finite simple group.