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 (Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia, 2014)We study the (Delta,D) and (Delta,N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by ...
Pérez Rosés, Hebert (Indonesian Combinatorial Society (InaCombS)Graph Theory and Applications (GTA) Research CentreUniversity of Newcastle (Australia)Institut Teknologi Bandung (ITB) (Indonesia), 2014)This paper discusses the most popular algebraic techniques and computational methods that have been used to construct large undirected graphs with given degree and diameter.
Holub, Přemys; Miller, Mirka; Pérez Rosés, Hebert; Ryan, Joe (Elsevier, 2014-08-23)The degree diameter problem involves finding the largest graph (in terms of the number of vertices) subject to constraints on the degree and the diameter of the graph. Beyond the degree constraint there is no restriction ...