✦ LIBER ✦

On digraphs with the odd cycle property

✍ Scribed by Rachel Manber; Jia-Yu Shao

Publisher: John Wiley and Sons
Year: 1986
Tongue: English
Weight: 462 KB
Volume: 10
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190100203

No coin nor oath required. For personal study only.

✦ Synopsis

We say that a digraph D has the odd cycle property if there exists an edge subset S such that every cycle of D has an odd number of edges from S. We give necessary and sufficient conditions for a digraph to have the odd cycle property. We also consider the analogous problem for graphs.

📜 SIMILAR VOLUMES

On the construction of odd cycle systems

✍ D. G. Hoffman; C. C. Lindner; C. A. Rodger 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 406 KB

Three obvious necessary conditions for the existence of a k-cycle system of order n are that if n > 1 then n 1 k, n is odd, and 2 k divides n(n -1). We show that if these necessary conditions are sufficient for all n satisfying k I n < 3k then they are sufficient for all n. In particular, there exis

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

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

A bound on the chromatic number using th

A bound on the chromatic number using the longest odd cycle length

✍ Sreyash Kenkre; Sundar Vishwanathan 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

## Abstract Let __G__ be a non‐bipartite graph with ℓ as the length of the longest odd cycle. Erdös and Hajnal proved that χ(__G__) ≤ ℓ + 1. We show that the only graphs for which this is tight are those that contain __K__~ℓ~ + 1 and further, if __G__ does not contain __K__~ℓ~ then χ(__G__) ≤ ℓ −1.

Note on the existence of directed (k + 1

Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs

✍ R. Balakrishnan; P. Paulraja 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k-partite (k 2 5) graph with each part of size at least 2 yield a directed (k + 1)-cycle?

On Codes with the Identifiable Parent Pr

On Codes with the Identifiable Parent Property

✍ Henk D.L Hollmann; Jack H van Lint; Jean-Paul Linnartz; Ludo M.G.M Tolhuizen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 217 KB

If C is a q-ary code of length n and a and b are two codewords, then c is called a descendant of a and b if c i # [a i , b i ] for i=1, ..., n. We are interested in codes C with the property that, given any descendant c, one can always identify at least one of the ``parent'' codewords in C. We study