Article
Full entry |
PDF
(1.1 MB)
Feedback
PDF
(1.1 MB)
Feedback
Summary:
The (directed) distance from a vertex $u$ to a vertex $v$ in a strong digraph $D$ is the length of a shortest $u$-$v$ (directed) path in $D$. The eccentricity of a vertex $v$ of $D$ is the distance from $v$ to a vertex furthest from $v$ in $D$. The radius rad$D$ is the minimum eccentricity among the vertices of $D$ and the diameter diam$D$ is the maximum eccentricity. A central vertex is a vertex with eccentricity $\mathop {\mathrm rad}\nolimits D$ and the subdigraph induced by the central vertices is the center $C(D)$. For a central vertex $v$ in a strong digraph $D$ with $\mathop {\mathrm rad}\nolimits D<\text{diam} D$, the central distance $c(v)$ of $v$ is the greatest nonnegative integer $n$ such that whenever $d(v,x)\le n$, then $x$ is in $C(D)$. The maximum central distance among the central vertices of $D$ is the ultraradius urad$D$ and the subdigraph induced by the central vertices with central distance urad$D$ is the ultracenter $UC(D)$. For a given digraph $D$, the problem of determining a strong digraph $H$ with $UC(H)=D$ and $C(H)\ne D$ is studied. This problem is also considered for digraphs that are asymmetric.
References:
[1] G. Chartrand, K. Novotny, and S.J. Winters: The ultracenter and central fringe of a graph. Networks (to appear). MR 1844442
[2] G. Chartrand, G.L. Johns, and S. Tian: Directed distance in digraphs: centers and peripheries. Congr. Numer. 89 (1992), 89–95. MR 1208943
[3] M.P. Shaikh: On digraphs with prescribed centers and peripheries. J. Undergrad. Math. 25 (1993), 31–42.
[4] S.J. Winters: Distance Associated with Subgraphs and Subdigraphs. Ph.D. Dissertation, Western Michigan University, 1993.
Search
Partner of
