𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dense bipartite digraphs

✍ Scribed by M. A. Fiol; J. L. A. Yebra

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
523 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For its implications in the design of interconnection networks, it is interesting to find

(a) (di)graphs with given maximum (out‐)degree d and diameter D that have large order;

(b) (di)graphs of given order and maximum (out‐)degree d that have small diameter.

(Di)graphs of either type are often called dense.

This paper considers the case of bipartite digraphs. For problem (a) it is shown that a Moore‐like bound on the order of such digraphs can be (and in fact is) attained only when D ≤ 4. For D > 4 a construction is presented that yields a family of bipartite digraphs with order larger than (d^4^ — 1)/d^4^ times the above‐mentioned bound. For problem (b) an appropriate lower bound is derived and a construction is presented that provides bipartite digraphs of any (even) order whose diameter does not exceed this lower bound in more than one.

📜 SIMILAR VOLUMES

On Moore bipartite digraphs
On Moore bipartite digraphs
✍ M. A. Fiol; J. Gimbert; J. Gómez; Y. Wu 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter __k__ and the maximum out‐degrees (__d__~1~, __d__~2~) of its partite sets of vertic

On super-edge-connected digraphs and bip
On super-edge-connected digraphs and bipartite digraphs
✍ M. A. Fiol 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 524 KB

## Abstract A maximally edge‐connected digraph is called super‐λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super‐λ are presented in terms of parameters such as diamet

Local Strongly Arc-Connectivity in Regul
Local Strongly Arc-Connectivity in Regular Bipartite Digraphs
✍ J.M. Xu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 99 KB

We show that for any vertex \(x\) of a \(d\)-regular bipartite digraph there are a vertex \(y\), in the other class of the bipartition, and \(d(x, y)\)-paths and \(d(y, x)\)-paths such that all \(2 d\) of them are pairwise arc-disjoint. This result generalizes a theorem of Hamidoune and Las Vergnas

The Minimum Spanning Strong Subdigraph P
The Minimum Spanning Strong Subdigraph Problem for Extended Semicomplete Digraphs and Semicomplete Bipartite Digraphs
✍ Jørgen Bang-Jensen; Anders Yeo 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 148 KB

We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the