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

For an ordered set $W=\{w_1,w_2,...,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector $$\mathrm{code}\left(v\right)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$$ where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\mathrm{code}\left(u\right)\ne \mathrm{code}\left(v\right)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric $k$-set is the local metric dimension $\mathrm{lmd}\left(G\right)$ of $G$. A local metric set of $G$ of cardinality $\mathrm{lmd}\left(G\right)$ is a local metric basis of $G$. We characterize all nontrivial connected...

In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. The median problem of graphs is closely related to the optimization problems involving the placement of network servers, the core of the entire networks. Bipartite graphs play a significant role in designing very large interconnection networks. In this paper, we...

The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S ⊆ V (G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i. In this note, we determine the path-distance-width of hypercubes.

The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like...

Let $L(n,d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d.$ Lesniak (1975) gave the lower bound $B(n,d)=\lceil 2(n-1)/d\rceil$ for $L(n,d).$ When $d$ is even, $B(n,d)=L(n,d).$ But when $d$ is odd, $B(n,d)$ is smaller than $L(n,d)$ in general. For example, $B(21,3)=14$ while $L(21,3)=19.$ In this note, we determine $L(n,d)$ using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = ∑u,v∈V(G) d(u, v) where dG(u, v) is the distance between vertices u and v of G. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and S ⊆ V (G), the Steiner distance d(S) of the vertices of S is the minimum size of a connected subgraph whose vertex set is S. We now...

The strong isometric dimension of a reflexive graph is related to its injective hull: both deal with embedding reflexive graphs in the strong product of paths. We give several upper and lower bounds for the strong isometric dimension of general graphs; the exact strong isometric dimension for cycles and hypercubes; and the isometric dimension for trees is found to within a factor of two.

A method to infer $X$-trees (valued trees having $X$ as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2$n$-3 distance values between the $n$ elements of $X$, if they fulfill some explicit conditions. This construction is based on the mapping between $X$-tree and a weighted generalized 2-tree spanning $X$.

A method to infer X-trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2n-3 distance values between the n elements of X, if they fulfill some explicit conditions. This construction is based on the mapping between X-tree and a weighted generalized 2-tree spanning X.

For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s{v}_1,v_2,...,v_n$ of vertices of $G$, define $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$. The traceable number $t\left(G\right)$ of a graph $G$ is $t\left(G\right)=min\left\{d\right(s\left)\right\}$ and the upper traceable number $t^{+}\left(G\right)$ of $G$ is $t^{+}\left(G\right)=max\left\{d\left(s\right)\right\},$ where the minimum and maximum are taken over all linear orderings $s$ of vertices of $G$. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs $G$ for which $t^{+}\left(G\right)-t\left(G\right)=1$ are characterized and a formula for the upper...

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_D\left[S\right]={\bigcup }_{x,y\in S}{I}_D[x,y]$. A set S of vertices is a detour convex set if $I_D\left[S\right]=S$. The detour convex hull ${\left[S\right]}_D$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of V(G) with ${\left[S\right]}_D=V\left(G\right)$....

For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic numbers...

Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs having a distinguished or root vertex, labeled 0. The hierarchical product G2 ⊓ G1 of G2 and G1 is a graph with vertex set V2 × V1. Two vertices y2y1 and x2x1 are adjacent if and only if y1x1 ∈ E1 and y2 = x2; or y2x2 ∈ E2 and y1 = x1 = 0. In this paper, the Wiener, eccentric connectivity and Zagreb indices of this new operation of graphs are computed. As an application, these topological indices for a class of alkanes are computed. ACM Computing...