✦ LIBER ✦

Directed Triangles in Digraphs

✍ Scribed by Jian Shen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 144 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1839

No coin nor oath required. For personal study only.

✦ Synopsis

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 note, we prove that c 3&-7=0.3542....

📜 SIMILAR VOLUMES

Maximum directed cuts in acyclic digraph

Maximum directed cuts in acyclic digraphs

✍ Noga Alon; Béla Bollobás; András Gyárfás; Jenő Lehel; Alex Scott 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract It is easily shown that every digraph with __m__ edges has a directed cut of size at least __m__/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in __acyclic__ digraphs, and prove a number of related results concerning cuts

Maximum directed cuts in digraphs with d

Maximum directed cuts in digraphs with degree restriction

✍ Jenö Lehel; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract For integers __m, k__≥1, we investigate the maximum size of a directed cut in directed graphs in which there are __m__ edges and each vertex has either indegree at most __k__ or outdegree at most __k__. © 2009 Wiley Periodicals, Inc. J Graph Theory

Even Directed Cycles inH-Free Digraphs

✍ Anna Galluccio; Martin Loebl 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 176 KB

A digraph is H-free if its underlying graph does not contain a subgraph contractible to the graph H. We provide a polynomial-time algorithm to solve the even cycle problem in the class of K -free digraphs and in the class of K -free 3, 3 5 digraphs. We also discuss the important role played by the s

Girth in digraphs

✍ J. C. Bermond; A. Germa; M. C. Heydemann; D. Sotteau 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

## 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.

Triangles in 2-factorizations

✍ Dejter, I. J.; Franek, F.; Mendelsohn, E.; Rosa, A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 3 views

The triangle-spectrum for 2-factorizations of the complete graph K v is the set of all numbers δ such that there exists a 2-factorization of K v in which the total number of triangles equals δ. By applying mainly design-theoretic methods, we determine the triangle spectrum for all v ≡ 1 or 3 (mod 6)

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