𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Unilaterally connected large digraphs and generalized cycles

✍ Scribed by José Gómez; Eduardo A. Canale; Xavier Muñoz

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
161 KB
Volume
42
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Lower and upper bounds on the order of digraphs and generalized p‐cycles with a specified maximum degree and unilateral diameter are given for generic values of the parameters. Infinite families of digraphs attaining the bounds asymptotically or even exactly are presented. In particular, optimal results are proved for bipartite digraphs (p = 2) and digraphs with unilateral diameter 3. © 2003 Wiley Periodicals, Inc.

📜 SIMILAR VOLUMES

The connectivity of large digraphs and g
The connectivity of large digraphs and graphs
✍ M. A. Fiol 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 632 KB

## Abstract This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order __n__, minimum degree δ, maximum degree Δ, diameter __D__, and a new parameter l~pi;~, __0__ ≤ π ≤ δ − 2, related with the number of short paths (in the case of graphs

Connectivity of large bipartite digraphs
Connectivity of large bipartite digraphs and graphs
✍ M.C. Balbuena; A. Carmona; J. Fàbrega; M.A. Fiol 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 638 KB

This paper studies the relation between the connectivity and other parameters of a bipartite (di)graph G. Namely, its order n, minimum degree 6, maximum degree A, diameter D, and a new parameter f related to the number of short paths in G. (When G is a bipartite -undirected --graph this parameter tu

Orientations of hamiltonian cycles in la
Orientations of hamiltonian cycles in large digraphs
✍ Adam Paweł Wojda 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

We prove that, with some exceptions, every digraph with n 3 9 vertices and at least ( n -1) ( n -2) + 2 arcs contains all orientations of a Hamiltonian cycle.

Counting small cycles in generalized de
Counting small cycles in generalized de Bruijn digraphs
✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

In this paper, we count small cycles in generalized de Bruijn digraphs. Let n Å pd h , where d É / p, and g l Å gcd(d l 0 1, n). We show that if p õ d 3 and k °log d n / 1, or p ú d 3 and k °h / 3, then the number of cycles of length k in a generalized de Bruijn digraph G B (n, d) is given by 1/ k

Cycles through Large Degree Vertices in
Cycles through Large Degree Vertices in Digraphs: A Generalization of Meyniel's Theorem
✍ Kenneth A. Berman; Xin Liu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 191 KB

Let D=(V, E) be a digraph with vertex set V of size n and arc set E. For u # V, let d(u) denote the degree of u. A Meyniel set M is a subset of V such that d(u)+d(v) 2n&1 for every pair of nonadjacent vertices u and v belonging to M. In this paper we show that if D is strongly connected, then every