For a nonempty set $S$ of vertices in a strong digraph $D$, the strong distance $d\left(S\right)$ is the minimum size of a strong subdigraph of $D$ containing the vertices of $S$. If $S$ contains $k$ vertices, then $d\left(S\right)$ is referred to as the $k$-strong distance of $S$. For an integer $k\ge 2$ and a vertex $v$ of a strong digraph $D$, the $k$-strong eccentricity ${\mathrm{s}e}_k\left(v\right)$ of $v$ is the maximum $k$-strong distance $d\left(S\right)$ among all sets $S$ of $k$ vertices in $D$ containing $v$. The minimum $k$-strong eccentricity among the vertices of $D$ is its $k$-strong radius ${\mathrm{s}rad}_{k}D$ and the maximum...

A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...

Let G be a connected graph. For two vertices u and v in G, a u-v geodesic is any shortest path joining u and v. The closed geodetic interval IG[u, v] consists of all vertices of G lying on any u-v geodesic. For S ⊆ V (G), S is a geodetic set in G if ∪u,v∈S IG[u, v] = V (G). Vertices u and v of G are neighbors if u and v are adjacent. The closed neighborhood NG[v] of vertex v consists of v and all neighbors of v. For S ⊆ V (G), S is a dominating set in G if ∪u∈S NG[u] = V (G). A geodetic dominating...

A graph is called a partial cube if it admits an isometric embedding into a hypercube. Subdivisions of wheels are considered with respect to such embeddings and with respect to the convexity of their intervals. This allows us to answer in negative a question of Chepoi and Tardif from 1994 whether all bipartite graphs with convex intervals are partial cubes. On a positive side we prove that a graph which is bipartite, has convex intervals, and is not a partial cube, always contains a subdivision...

If $G$ is a connected graph with distance function $d$, then by a step in $G$ is meant an ordered triple $(u,x,v)$ of vertices of $G$ such that $d(u,x)=1$ and $d(u,v)=d(x,v)+1$. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.

We define digraphs minimal, critical, and maximal by three types of radii. Some of these classes are completely characterized, while for the others it is shown that they are large in terms of induced subgraphs.

The paper gives an overview of results for radially minimal, critical, maximal and stable graphs and digraphs.

By a signpost system we mean an ordered pair $(W,P)$, where $W$ is a finite nonempty set, $P\subseteq W\times W\times W$ and the following statements hold: $$\text{if}(u,v,w)\in P,\text{then}(v,u,u)\in P\text{and}(v,u,w)\notin P,\text{for}\text{all}u,v,w\in W;\text{if}u\ne v,i\text{then}\text{there}\text{exists}r\in W\text{such}\text{that}(u,r,v)\in P,\text{for}\text{all}u,v\in W.$$ We say that a signpost system $(W,P)$ is smooth if the folowing statement holds for all $u,v,x,y,z\in W$: if $(u,v,x),(u,v,z),(x,y,z)\in P$, then $(u,v,y)\in P$. We say thay a signpost system $(W,P)$ is simple if the following statement holds for all $u,v,x,y\in W$: if $(u,v,x),(x,y,v)\in P$, then $(u,v,y),(x,y,u)\in P$. By the underlying graph of a signpost system $(W,P)$ we mean the graph $G$ with $V\left(G\right)=W$ and such that the following statement holds for all distinct $u,v\in W$: $u$ and $v$ are adjacent in $G$ if and only if $(u,v,v)\in P$....

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 $\mathrm{r}adD$ and the subdigraph induced by the central vertices is the center $C\left(D\right)$. For a central vertex $v$ in a strong digraph...