✦ LIBER ✦

Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle

✍ Scribed by G.L. Ding; A. Schrijver; P.D. Seymour

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 203 KB
Volume: 58
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1993.1029

No coin nor oath required. For personal study only.

✦ Synopsis

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by P. D. Seymour. This paper gives a shorter proof of that result. " 1993 Academic Press. Inc.

📜 SIMILAR VOLUMES

Constructing the Graphs That Triangulate

Constructing the Graphs That Triangulate Both the Torus and the Klein Bottle

✍ Serge Lawrencenko; Seiya Negami 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 158 KB

We show how to construct all the graphs that can be embedded on both the torus and the Klein bottle as their triangulations.

Disjoint Cycles in Eulerian Digraphs and

Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs

✍ Richard A. Brualdi; Jian Shen 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 87 KB

denote the set of all m × n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) ] ". The interchange graph G(R, S) of A(R, S) was defined by Brualdi in 1980. It is the graph with all matrices in A(R, S) as its vertices and two matrices are adjacent provided they differ by

Disjoint circuits in the cartesian produ

Disjoint circuits in the cartesian product of two directed cycles

✍ Stephen Curran 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB

## Abstract We show that the Cartesian product of two directed cycles __Z__~__a__~ X __Z__~__b__~ has __r__ disjointly embedded circuits __C__~1~, __C__~2~, ⃛, __C__~r~ with specified knot classes knot__(C~i~) = (m~i~, n~i~)__, for __i__ = 1, 2, ⃛, __r__, if and only if there exist relatively prime

Hamiltonian cycles in bipartite quadrang

Hamiltonian cycles in bipartite quadrangulations on the torus

✍ Atsuhiro Nakamoto; Kenta Ozeki 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 2 views

## Abstract In this article, we shall prove that every bipartite quadrangulation __G__ on the torus admits a simple closed curve visiting each face and each vertex of __G__ exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on th

On the cycle polytope of a directed grap

On the cycle polytope of a directed graph and its relaxations

✍ Egon Balas; Rüdiger Stephan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

On hamiltonian cycles in the prism over

On hamiltonian cycles in the prism over the odd graphs

✍ Letícia R. Bueno; Peter Horák 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

The Kneser graph K (n, k) has as its vertex set all k-subsets of an n-set and two k-subsets are adjacent if they are disjoint. The odd graph O k is a special case of Kneser graph when n = 2k +1. A long standing conjecture claims that O k is hamiltonian for all k>2. We show that the prism over O k is