The (∆,D) and (∆,N) problems in double-step digraphs with unilateral distance

View/ Open
Issue date
2014Suggested citation
Dalfó, Cristina;
Fiol, Miguel Angel;
.
(2014)
.
The (∆,D) and (∆,N) problems in double-step digraphs with unilateral distance.
Electronic Journal of Graph Theory and Applications, 2014, vol. 2, núm. 1, p. 1–17.
https://doi.org/10.5614/ejgta.2014.2.1.1.
Metadata
Show full item recordAbstract
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 changing the directions of all the arcs.
The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree $\Delta$ and the unilateral diameter D*, whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices.
Moreover, we compute the mean unilateral distance of the digraphs in the families considered.
Is part of
Electronic Journal of Graph Theory and Applications, 2014, vol. 2, núm. 1, p. 1–17European research projects
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as cc-by-sa (c) C. Dalfo et al., 2014
Related items
Showing items related by title, author, creator and subject.
-
The Manhattan Product of Digraphs
Comellas, Francesc; 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, 2013)We study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other ... -
From Subkautz Digraphs to Cyclic Kautz Digraphs
Dalfó, Cristina (World Scientific Publishing, 2018)Kautz digraphs K(d, l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, l) were recently introduced by ... -
Sequence Mixed Graphs
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 ...