For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset...

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by ${\gamma }_{\mathrm{pr}}\left(G\right)$, is the minimum cardinality of a paired-dominating set of $G$. The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of degree one,...

For a vertex $v$ of a connected oriented graph $D$ and an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices of $D$, the (directed distance) representation of $v$ with respect to $W$ is the ordered $k$-tuple $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(v,w_i)$ is the directed distance from $v$ to $w_i$. The set $W$ is a resolving set for $D$ if every two distinct vertices of $D$ have distinct representations. The minimum cardinality of a resolving set for $D$ is the (directed distance) dimension $dim\left(D\right)$ of $D$. The dimension of a connected oriented graph need not be defined. Those oriented graphs...

By a ternary structure we mean an ordered pair $(U_0,T_0)$, where $U_0$ is a finite nonempty set and $T_0$ is a ternary relation on $U_0$. A ternary structure $(U_0,T_0)$ is called here a directed geodetic structure if there exists a strong digraph $D$ with the properties that $V\left(D\right)=U_0$ and $$T_0(u,v,w)\text{if}\text{and}\text{only}\text{if}{d}_D(u,v)+d_D(v,w)=d_D(u,w)$$ for all $u,v,w\in U_0$, where $d_D$ denotes the (directed) distance function in $D$. It is proved in this paper that there exists no sentence $𝐬$ of the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies...

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there...

For a nontrivial connected graph G = (V(G),E(G)), a set S⊆ V(G) is called an edge geodetic set of G if every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g₁(G) of G is the minimum order of its edge geodetic sets. Bounds for the edge geodetic number of Cartesian product graphs are proved and improved upper bounds are determined for a special class of graphs. Exact values of the edge geodetic number of Cartesian product are obtained for several...

For two vertices $u$ and $v$ of a connected graph $G$, the set $I(u,v)$ consists of all those vertices lying on a $u$–$v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I(u,v)$ for $u,v\in S$ is denoted by $I\left(S\right)$. A set $S$ is a convex set if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $\left|S\right|=\mathrm{c}on\left(G\right)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum convex set...

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)$ = ($d(v,w_1),d(v,w_2),\cdots ,d(v,w_k)$), where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations. A resolving set of minimum cardinality is a basis for $G$ and the number of vertices in a basis is its (metric) dimension $dim\left(G\right)$. For a basis $W$ of $G$, a subset $S$ of $W$ is called a forcing subset of $W$ if $W$ is...

For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic...

For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The...

For two vertices u and v of a connected graph G, the set $I_G[u,v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_G[u,v]$ for u,v ∈ S is denoted by $I_G\left[S\right]$. A set S ⊆ V(G) is a geodetic set if $I_G\left[S\right]=V\left(G\right)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

The Gutman index and the edge-Wiener index have been extensively investigated particularly in the last decade. An important stream of re- search on graph indices is to bound indices in terms of the order and other parameters of given graph. In this paper we present asymptotically sharp upper bounds on the Gutman index and the edge-Wiener index for graphs of given order and vertex-connectivity κ, where κ is a constant. Our results substantially generalize and extend known results in the area.

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector $$c_W\left(v\right)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k)).$$ The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathrm{i}r\left(G\right)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathrm{i}r\left(G\right)=1$, $n-1$,...

The interval function (in the sense of H. M. Mulder) is an important tool for studying those properties of a connected graph that depend on the distance between vertices. An axiomatic characterization of the interval function of a connected graph was published by Nebeský in 1994. In Section 2 of the present paper, a simpler and shorter proof of that characterization will be given. In Section 3, a characterization of geodetic graphs will be established; this characterization will utilize properties...

For a nontrivial connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. Detour distance is a metric on the vertex set of $G$. For each integer $k$ with $1\le k\le n-1$, a coloring $c:V\left(G\right)\to \mathbb{N}$ is a $k$-metric coloring of $G$ if $\left|c\right(u)-c(v\left)\right|+D(u,v)\ge k+1$ for every two distinct vertices $u$ and $v$ of $G$. The value ${\chi }_m^k\left(c\right)$ of a $k$-metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$-metric chromatic number ${\chi }_m^k\left(G\right)$ of $G$ is the minimum value of a $k$-metric coloring of $G$. For every...