- Title
- Characterization of eccentric digraphs
- Creator
- Gimbert, Joan; Lopez, Nacho; Miller, Mirka; Ryan, Joe
- Date
- 2006
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/42118
- Identifier
- vital:332
- Identifier
-
https://doi.org/10.1016/j.disc.2005.11.015
- Identifier
- ISSN:0012-365X
- Abstract
- 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.; C1
- Publisher
- Elsevier
- Relation
- Discrete Mathematics Vol. 306, no. 2 (2006), p. 210-219
- Rights
- Copyright Elsevier
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; Distance; Eccentric digraph; Eccentric vertex; Eccentricity; Information theory; Mathematical models; Graph theory
- Reviewed
- Hits: 1819
- Visitors: 1781
- Downloads: 3
| Thumbnail | File | Description | Size | Format |
|---|