On strong digraphs with a prescribed ultracenter

Chartrand, Gary ; Gavlas, Heather ; Schulz, Kelly ; Winters, Steve J.

Czechoslovak Mathematical Journal, Tome 47 (1997) no. 1, pp. 83-94

Résumé

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.

Détail

Classification : 05C12, 05C20