×

A line digraph of a complete bipartite digraph. (English) Zbl 1225.05118

Summary: 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aigner, M., On the line graph of a directed graph, Math. Z., 102, 15-29 (1967)
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London, (Elsevier, New York) · Zbl 1134.05001
[3] Broersma, H. J., Bipartite regular graph with fixed diameter, Networks, 26, 3, 139-144 (2005) · Zbl 0855.05072
[4] Fiol, M. A.; Gimbert, J.; Gómez, J.; Wu, Y., On Moore bipartite digraphs, J. Graph Theory, 43, 171-187 (2003) · Zbl 1036.05025
[5] Fiol, M. A.; Gimbert, J.; Miller, M., Multipartite Moore digraphs, Linear Algebra Appl., 419, 234-250 (2006) · Zbl 1105.05028
[6] Fiol, M. A.; Yebra, J. L.A., Dense bipartite digraphs, J. Graph Theory, 14, 687-700 (1990) · Zbl 0725.05044
[7] Fiol, M. A.; Yebra, J. L.A., Line digraph iterations and \((d, k)\) digraph problem, IEEE Trans. Comput., 33, 5, 400-403 (1984) · Zbl 0528.68048
[8] Finck, H. J.; Grahmann, G., Vollständiges Produkt, Chromatische Zahl und Charakteristisches Polynom Regulärer Graphen, I. Wiss. Z. TH Ilmenau, 11, 1-3 (1965) · Zbl 0132.20801
[9] Gómez, J.; Padró, C.; Perennes, S., Large generalized cycles, Discrete Appl. Math., 89, 1-3, 107-123 (1998) · Zbl 0919.05035
[10] Lin, G. N.; Zhang, F. J., The characteristic polynomial of line digraph and a type of cospectral digraphs, KeXue TongBao, 22, 1348-1350 (1983)
[11] Xu, J. M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1046.68026
[12] Zhang, Z.; Liu, F.; Meng, J., Super-connected \(n\)-th iterated line digraphs, OR Trans., 9, 2, 35-39 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.