𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Compatible Euler Tours and Supplementary Eulerian Vectors

✍ Scribed by André Bouchet

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
276 KB
Volume
14
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

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 polynomial-time algorithm, and we give a min-max relation generalizing Jackson's theorem. The solution uses the theory of isotropic systems by replacing Euler tours by supplementary Eulerian vectors.

📜 SIMILAR VOLUMES

Compatible Euler tours for transition sy
Compatible Euler tours for transition systems in Eulerian graphs
✍ Bill Jackson 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 277 KB

We show that ff G is an Eulerian graph of minimum degree 2k, then G has a set S of k -2 Euler tours such that each pair of adjacent edges of G is consecutive in at most one tour of S. We conjecture that our bound of k -2 may be improved to 2k -2.

Cycles containing matchings and pairwise
Cycles containing matchings and pairwise compatible euler tours
✍ Bill Jackson; Nicholas C. Wormald 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

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