✦ LIBER ✦

Cycles of Prescribed Modularity in Planar Digraphs

✍ Scribed by Anna Galluccio; Martin Loebl

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 252 KB
Volume: 21
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0036

No coin nor oath required. For personal study only.

✦ Synopsis

We present a polynomial-time algorithm to find out whether all directed cycles in a directed planar graph are of length p mod q, with 0 F pq.

📜 SIMILAR VOLUMES

Orientations of hamiltonian cycles in la

Orientations of hamiltonian cycles in large digraphs

✍ Adam Paweł Wojda 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

We prove that, with some exceptions, every digraph with n 3 9 vertices and at least ( n -1) ( n -2) + 2 arcs contains all orientations of a Hamiltonian cycle.

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

Cycles through Large Degree Vertices in

Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem

✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

On the existence of a specified cycle in

On the existence of a specified cycle in digraphs with constraints on degrees

✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by