Show More

Show Less

Characterization of eccentric digraphs

- Gimbert, Joan, Lopez, Nacho, Miller, Mirka, Ryan, Joe

**Authors:**Gimbert, Joan , Lopez, Nacho , Miller, Mirka , Ryan, Joe**Date:**2006**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 306, no. 2 (2006), p. 210-219**Full Text:**false**Reviewed:****Description:**The eccentric digraph ED(G) of a digraph G represents the binary relation, defined on the vertex set of G, of being 'eccentric'; that is, there is an arc from u to v in ED(G) if and only if v is at maximum distance from u in G. A digraph G is said to be eccentric if there exists a digraph H such that G=ED(H). This paper is devoted to the study of the following two questions: what digraphs are eccentric and when the relation of being eccentric is symmetric. We present a characterization of eccentric digraphs, which in the undirected case says that a graph G is eccentric iff its complement graph G is either self-centered of radius two or it is the union of complete graphs. As a consequence, we obtain that all trees except those with diameter 3 are eccentric digraphs. We also determine when ED(G) is symmetric in the cases when G is a graph or a digraph that is not strongly connected. Crown Copyright © 2006 Published by Elsevier B.V. All rights reserved.**Description:**C1**Description:**2003001601

- Fiol, M. A., Gimbert, Joan, Miller, Mirka

**Authors:**Fiol, M. A. , Gimbert, Joan , Miller, Mirka**Date:**2006**Type:**Text , Journal article**Relation:**Linear Algebra and Its Applications Vol. 419, no. 1 (2006), p. 234-250**Full Text:**false**Reviewed:****Description:**We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.**Description:**C1**Description:**2003002157

- Nguyen, Minh Hoang, Miller, Mirka, Gimbert, Joan

**Authors:**Nguyen, Minh Hoang , Miller, Mirka , Gimbert, Joan**Date:**2007**Type:**Text , Journal article**Relation:**Discrete Mathematics Vol. 307, no. 7-8 (2007), p. 964-970**Full Text:**false**Reviewed:****Description:**The Moore bound for a directed graph of maximum out-degree d and diameter k is M**Description:**C1**Description:**2003005024

- «
- ‹
- 1
- ›
- »

Are you sure you would like to clear your session, including search history and login status?