✦ LIBER ✦

Supereulerian graphs: A survey

✍ Scribed by Paul A. Catlin

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 996 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160209

No coin nor oath required. For personal study only.

✦ Synopsis

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 number of a graph. We outline the research on supereulerian graphs, the reduction method, and its applications.

📜 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

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

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.

Packing of graphs—a survey

✍ H.P. Yap 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 630 KB

Coloring graph products — A survey

✍ Sandi Klavẑar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 564 KB

There are four standard products of graphs: the direct product, the Cartesian product, the strong product and the lexicographic product. The chromatic number turned out to be an interesting parameter on all these products, except on the Cartesian one. A survey is given on the results concerning the