Abstract | ||
---|---|---|
The eccentric digraphED(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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.disc.2005.11.015 | Discrete Mathematics |
Keywords | Field | DocType |
eccentric vertex,distance,eccentric digraph,eccentricity | Discrete mathematics,Complete graph,Combinatorics,Vertex (geometry),Eccentric,Binary relation,Directed graph,Strongly connected component,Mathematics,Digraph,Complement graph | Journal |
Volume | Issue | ISSN |
306 | 2 | Discrete Mathematics |
Citations | PageRank | References |
2 | 0.40 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joan Gimbert | 1 | 46 | 6.62 |
Nacho López | 2 | 43 | 9.42 |
Mirka Miller | 3 | 530 | 90.29 |
Joseph Ryan | 4 | 37 | 3.71 |