✦ LIBER ✦

On the number of cycles possible in digraphs with large girth

✍ Scribed by Eric W. Allender

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 682 KB
Volume: 10
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(85)90044-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

The number of cycle lengths in graphs of

The number of cycle lengths in graphs of given minimum degree and girth

✍ P. Erdős; R.J. Faudree; C.C. Rousseau; R.H. Schelp 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 333 KB

This paper determines lower bounds on the number of different cycle lengths in a graph of given minimum degree k and girth g. The most general result gives a lower bound of ck ~.

On the number of quasi-kernels in digrap

On the number of quasi-kernels in digraphs

✍ Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

## Abstract A vertex set __X__ of a digraph __D__ = (__V, A__) is a __kernel__ if __X__ is independent (i.e., all pairs of distinct vertices of __X__ are non‐adjacent) and for every __v__ ∈ __V__‐__X__ there exists __x__ ∈ __X__ such that __vx__ ∈ __A__. A vertex set __X__ of a digraph __D__ = (__V

On the bipartite density of regular grap

On the bipartite density of regular graphs with large girth

✍ Ondřej Zýka 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 1 views

## Abstract Let __B(G)__ be the edge set of a bipartite subgraph of a graph __G__ with the maximum number of edges. Let __b~k~__ = inf{|__B(G)__|/|__E(G)__‖__G__ is a cubic graph with girth at least __k__}. We will prove that lim~k → ∞~ __b~k~__ ≥ 6/7.

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