For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)$ = ($d(v, w_1)$, $d(v, w_2),\dots ,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 with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $\dim (G)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph $<W>$ induced by $W$ is a nontrivial connected subgraph of $G$. The minimum cardinality of a connected resolving set in a graph $G$ is its connected resolving number $\mathop {\mathrm cr}(G)$. Thus $1 \le \dim (G) \le \mathop {\mathrm cr}(G) \le n-1$ for every connected graph $G$ of order $n \ge 3$. The connected resolving numbers of some well-known graphs are determined. It is shown that if $G$ is a connected graph of order $n \ge 3$, then $\mathop {\mathrm cr}(G) = n-1$ if and only if $G = K_n$ or $G = K_{1, n-1}$. It is also shown that for positive integers $a$, $b$ with $a \le b$, there exists a connected graph $G$ with $\dim (G) = a$ and $\mathop {\mathrm cr}(G) = b$ if and only if $(a, b) \notin \lbrace
(1, k)\: k = 1\hspace{5.0pt}\text{or}\hspace{5.0pt}k \ge 3\rbrace $. Several other realization results are present. The connected resolving numbers of the Cartesian products $G \times K_2$ for connected graphs $G$ are studied.
For an ordered k-decomposition D = {G1, G2, . . . , Gk} of a connected graph G and an edge e of G, the D-code of e is the k-tuple cD(e) = (d(e, G1), d(e, G2), . . . , d(e, Gk)), where d(e, Gi) is the distance from e to Gi . A decomposition D is resolving if every two distinct edges of G have distinct D-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dimd(G). A resolving decomposition D of G is connected if each Gi is connected for 1 ≤ i ≤ k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 ≤ dimd(G) ≤ cd(G) ≤ m for every connected graph G of size m ≥ 2. All nontrivial connected graphs with connected decomposition number 2 or m are characterized. We provide bounds for the connected decomposition number of a connected graph in terms of its size, diameter, girth, and other parameters. A formula for the connected decomposition number of a nonpath tree is established. It is shown that, for every pair a, b of integers with 3 ≤ a ≤ b, there exists a connected graph G with dimd(G) = a and cd(G) = b.
For a connected graph G of order n > 3 and an ordering s : v1, v2, . . . , vn of the vertices of G, d(s) = n−1 ∑ i=1 d(vi , vi+1), where d(vi , vi+1) is the distance between vi and vi+1. The traceable number t(G) of G is defined by t(G) = min {d(s)} , where the minimum is taken over all sequences s of the elements of V (G). It is shown that if G is a nontrivial connected graph of order n such that l is the length of a longest path in G and p is the maximum size of a spanning linear forest in G, then 2n−2−p ≤ t(G) ≤ 2n−2−l and both these bounds are sharp. We establish a formula for the traceable number of every tree in terms of its order and diameter. It is shown that if G is a connected graph of order n ≥ 3, then t(G) ≤ 2n − 4. We present characterizations of connected graphs of order n having traceable number 2n − 4 or 2n − 5. The relationship between the traceable number and the Hamiltonian number (the minimum length of a closed spanning walk) of a connected graph is studied. The traceable number t(v) of a vertex v in a connected graph G is defined by t(v) = min{d(s)}, where the minimum is taken over all linear orderings s of the vertices of G whose first term is v. We establish a formula for the traceable number t(v) of a vertex v in a tree. The Hamiltonian-connected number hcon(G) of a connected graph G is defined by hcon(G) = ∑ v∈V (G) t(v). We establish sharp bounds for hcon(G) of a connected graph G in terms of its order.
For an ordered $k$-decomposition $\mathcal D = \lbrace G_1, G_2,\dots , G_k\rbrace $ of a connected graph $G$ and an edge $e$ of $G$, the $\mathcal D$-code of $e$ is the $k$-tuple $c_{\mathcal D}(e) = (d(e, G_1), d(e, G_2),\ldots , d(e, G_k))$, where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition $\mathcal D$ is resolving if every two distinct edges of $G$ have distinct $\mathcal D$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\dim _d(G)$. A resolving decomposition $\mathcal D$ of $G$ is connected if each $G_i$ is connected for $1 \le i \le k$. The minimum $k$ for which $G$ has a connected resolving $k$-decomposition is its connected decomposition number $\mathop {\mathrm cd}(G)$. Thus $2 \le \dim _d(G) \le \mathop {\mathrm cd}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs of size $m$ with connected decomposition number 2 or $m$ have been characterized. We present characterizations for connected graphs of size $m$ with connected decomposition number $m-1$ or $m-2$. It is shown that each pair $s, t$ of rational numbers with $ 0 < s \le t \le 1$, there is a connected graph $G$ of size $m$ such that $\dim _d(G)/m = s$ and $\mathop {\mathrm cd}(G) / m = t$.
Let D be an oriented graph of order n and size m. A γ-labeling of D is a one-to-one function f : V (D) → {0, 1, 2, . . . , m} that induces a labeling f ' : E(D) → {±1, ±2, . . . , ±m} of the arcs of D defined by f ' (e) = f(v) − f(u) for each arc e = (u, v) of D. The value of a γ-labeling f is val(f) = ∑ e∈E(G) f ' (e). A γ-labeling of D is balanced if the value of f is 0. An oriented graph D is balanced if D has a balanced labeling. A graph G is orientably balanced if G has a balanced orientation. It is shown that a connected graph G of order n ≥ 2 is orientably balanced unless G is a tree, n ≡ 2 (mod 4), and every vertex of G has odd degree.
For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s\: v_1, v_2, \ldots , v_n$ of vertices of $G$, define $d(s) = \sum _{i=1}^{n-1} d(v_i, v_{i+1})$. The traceable number $t(G)$ of a graph $G$ is $t(G) = \min \lbrace d(s)\rbrace $ and the upper traceable number $t^+(G)$ of $G$ is $t^+(G) = \max \lbrace d(s)\rbrace ,$ 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^+(G)- t(G) = 1$ are characterized and a formula for the upper traceable number of a tree is established.