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

Dalfó, Cristina; Fiol, Miguel Angel

doi:https://doi.org/10.5614/ejgta.2014.2.1.1

View/Open

028096.pdf (568.6Kb)

Issue date

2014

Author

Dalfó, Cristina

Fiol, Miguel Angel

Suggested 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.

Abstract

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.

URI

http://hdl.handle.net/10459.1/65705

DOI

https://doi.org/10.5614/ejgta.2014.2.1.1

Is part of

Electronic Journal of Graph Theory and Applications, 2014, vol. 2, núm. 1, p. 1–17

Collections

The following license files are associated with this item:

Creative Commons

Except where otherwise noted, this item's license is described as cc-by-sa (c) C. Dalfo et al., 2014