✦ LIBER ✦

Girth in digraphs

✍ Scribed by J. C. Bermond; A. Germa; M. C. Heydemann; D. Sotteau

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 211 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040311

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For an integer k > 2, the best function m(n, k) is determined such that every strong digraph of order n with at least m(n, k) arcs contains a circuit of length k or less.

📜 SIMILAR VOLUMES

Diameter vulnerability of iterated line

Diameter vulnerability of iterated line digraphs in terms of the girth

✍ C. Balbuena; X. Marcote; D. Ferrero 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

Packing paths in digraphs

✍ Richard C. Brewster; Pavol Hell; Sarah H. Pantel; Romeo Rizzi; Anders Yeo 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract Let ${\cal G}$ be a fixed set of digraphs. Given a digraph __H__, a ${\cal G}$‐packing in __H__ is a collection ${\cal P}$ of vertex disjoint subgraphs of __H__, each isomorphic to a member of ${\cal G}$. A ${\cal G}$‐packing ${\cal P}$ is __maximum__ if the number of vertices belonging

Fractional Kernels in Digraphs

✍ Ron Aharoni; Ron Holzman 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We define a fractional version of the notion of ``kernels'' in digraphs and prove that every clique acyclic digraph (i.e., one in which no clique contains a cycle) has a fractional kernel. Using this we give a short proof of a recent result of Boros and Gurvich (proving a conjecture of Berge and Duc

Directed Triangles in Digraphs

✍ Jian Shen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 144 KB

Let c be the smallest possible value such that every digraph on n vertices with minimum outdegree at least cn contains a directed triangle. It was conjectured by Caccetta and Ha ggkvist in 1978 that c=1Â3. Recently Bondy showed that c (2 -6&3)Â5=0.3797... by using some counting arguments. In this no

Circumference and girth

✍ Cun-Quan Zhang 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB

Let G be 2-connected graph with girth g and minimum degree d. Then each, pair of verticfs of G is joined by a path of length a t least maxi? (dl)g, ( d -?) (g -4) + 2) if g B 4, and the length of a longest cycle of G is at least max{[(d -1) (g -2) + 21, [(2d -3) (g -4) + 41).

Hypotraceable digraphs

✍ Martin Grötschel; Carsten Thomassen; Yoshiko Wakabayashi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract A hypotraceable digraph is a digraph __D__ = (__V, E__) which is not traceable, i.e., does not contain a (directed)Hamiltonian path, but for which __D__ ‐ __v__ is traceable for all __ve__ ∈ __V__. We prove that a hypotraceable digraph of order __n__ exists iff __n__ ≥ 7 and that for ea