✦ LIBER ✦

On digraphs without antidirected cycles

✍ Scribed by Douglas D. Grant; F. Jaeger; C. Payan

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 259 KB
Volume: 6
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190060207

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n − 1)] ≤ t(n) ≤ 1/2 (n − 1) for n ≥ 5. Let t~r~ (n) denote the corresponding quantity for r‐colorable digraphs. We show that [16/5(n − 1)] ≤ t~5~(n) ≤ t~6~(n) ≤ 10/3(n − 1) for n ≥ 5 and that t~4~(n) = 3(n − 1) for n ≥ 3.

📜 SIMILAR VOLUMES

On cycles and paths in digraphs

✍ M.C. Heydemann 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 273 KB

The purpose of this communication is to announce some slrfficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].

On complementary cycles in locally semic

On complementary cycles in locally semicomplete digraphs

✍ Yubao Guo; Lutz Volkmann 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 440 KB

In this paper we show that a 2-connected locally semicomplete digraph of order at least 8 is not cycle complementary if and only if it is 2-diregular and has odd order. This result yields immediately two conjectures of Bang-Jensen.

On digraphs with the odd cycle property

✍ Rachel Manber; Jia-Yu Shao 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 462 KB

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.

On complete strongly connected digraphs

On complete strongly connected digraphs with the least number of 3-cycles

✍ M. Burzio; J. Pelant 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 186 KB

The least number of 3-cycles (cycles of length 3) that a hamiltonian tournament of order n can contain is n -2 (see [3]). Since each complete strongly connected digraph contains a spanning hamiltonian subtournament (see [2]), n-2 is also the least number of 3-cycles for these digraphs. In this pape

On the structure of complete graphs with

On the structure of complete graphs without alternating cycles

✍ C.C. Chen 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 139 KB

Note on graphs without repeated cycle le

Note on graphs without repeated cycle lengths

✍ Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general cas