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...

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum. Vol. 7 (2O02) no. 26. 1280-1294]. The adjaceni eccentric distance sum index of the graph G is defined as [...] where ε(υ) is the eccentricity of the vertex υ, deg(υ) is the degree of the vertex υ and D(υ) = ∑u∊v(G) d (u,υ)is the sum...

For any graph $G$, let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B(G,L(G),\mathrm{N}INC)$ of $G$ is a graph with vertex set $V\left(G\right)\cup E\left(G\right)$ and two vertices in $B(G,L(G),\mathrm{N}INC)$ are adjacent if and only if they correspond to two adjacent vertices of $G$, two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$. For brevity, this graph is denoted by $B_1\left(G\right)$. In this paper, structural properties of $B_1\left(G\right)$ and its complement including traversability and eccentricity properties are studied. In addition,...

An axiomatic characterization of the distance function of a connected graph is given in this note. The triangle inequality is not contained in this characterization.