๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A line digraph of a complete bipartite digraph

โœ Scribed by Juan Liu; Lin Sun; Jixiang Meng

Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
310 KB
Volume
22
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 outdegrees (d 1 , d 2 ) of its partite sets of vertices.

In this work, we define a family of dense digraphs, the diameter of which is not more than 1, comparable with that of the Moore bipartite digraph of the same order and maximum degree. Furthermore, some of its properties are given, such as the connectivity, spectrum and so on.

๐Ÿ“œ SIMILAR VOLUMES

Star-factorization of symmetric complete
Star-factorization of symmetric complete bipartite digraphs
โœ Kazuhiko Ushio ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 174 KB

We show that a necessary and sufficient condition for the existence of an Sk-factorization of the symmetric complete bipartite digraph K\*, is m = n -~ 0 (mod k(k -1)).

When a digraph and its line digraph are
When a digraph and its line digraph are connected and cospectral
โœ Fuji Zhang; Guoning Lin ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 266 KB

In this paper we characterize all digraphs each one of which is cospectral with its line digraph and both the digraph and its line digraph are connected. Some related enumeration problems are also considered. From these results we can see that there are arbitrarily large sets of cospectral digraphs.

Applying a proof of tverberg to complete
Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs
โœ Dan Pritikin ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 195 KB

Graham and Pollak 121 proved that n -1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K,, decompose. Tverberg 161, using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for

A Broadcasting Protocol in Line Digraphs
A Broadcasting Protocol in Line Digraphs
โœ Jean-Claude Bermond; Xavier Muรฑoz; Alberto Marchetti-Spaccamela ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 207 KB

We propose broadcasting algorithms for line digraphs in the telegraph model. The new protocols use a broadcasting protocol for a graph G to obtain a broadcasting protocol for the graph L k G, the graph obtained by applying k times, the line digraph operation to G. As a consequence improved bounds fo