✦ LIBER ✦

Cycles containing matchings and pairwise compatible euler tours

✍ Scribed by Bill Jackson; Nicholas C. Wormald

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 535 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140114

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let M be a matching in a graph G such that d(x) + d(y) ≥ |G| for all pairs of independent vertices x and y of G that are incident with M. We determine a necessary and sufficient condition for M to be contained in a cycle of G. This extends results of Häggkvist and Berman, and implies that if M is a 1‐factor of G and |G|  0 (mod 4), then M is contained in a Hamilton cycle of G. We use our results to deduce that an eulerian graph of minimum degree 2k contains k pairwise compatible Euler tours.

📜 SIMILAR VOLUMES

A characterisation of graphs having thre

A characterisation of graphs having three pairwise compatible Euler tours

✍ Bill Jackson 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 661 KB

On the maximum number of pairwise compat

On the maximum number of pairwise compatible euler cycles

✍ H. Fleischner; A. J. W. Hilton; Bill Jackson 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 629 KB

## Abstract B. Jackson [4] made the following conjecture: If __G__ is an Eulerian graph with δ(__G__) ≥ 2__k__, then __G__ has a set of 2__k__ ‐ 2 pairwise compatible Euler cycles (i.e., every pair of adjacent edges appears in at most one of these Euler cycles as a pair of consecutive edges). We ve

Compatible Euler Tours and Supplementary

Compatible Euler Tours and Supplementary Eulerian Vectors

✍ André Bouchet 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 276 KB

Two Euler tours of a graph \(G\) are compatible if no pair of adjacent edges of \(G\) are consecutive in both tours. Bill Jackson recently gave a good characterization of those 4-regular graphs which contain three pairwise compatible Euler tours. In this paper we give a solution by means of a polyno

Spanning trees, Euler tours, medial grap

Spanning trees, Euler tours, medial graphs, left-right paths and cycle spaces

✍ R.Bruce Richter 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 468 KB

A variety of algebraic relationships between the various objects in the title are obtained. For example, if a graph embedded in the projective plane has only one left-right path, then the number of spanning trees in the graph and its geometric dual have different parities and its medial has an odd n