Iterated line digraphs are asymptotically dense
MetadataShow full item record
We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs.
Is part ofLinear Algebra and its Applications, 2017, vol. 529, p. 391-396
European research projects
The following license files are associated with this item:
Showing items related by title, author, creator and subject.
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier, 2017)A mixed graph can be seen as a type of digraph containing some edges (or two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and iterated line ...
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio (Elsevier B.V., 2018)A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a ...
Dalfó, Cristina; Fiol, Miguel Angel; López Lorenzo, Ignacio; Ryan, Joe (Elsevier, 2020)We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can ...