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 ≤ k ≤ n−1, a coloring c : V (G) → N is a k-metric coloring of G if |c(u) − c(v)| + D(u, v) ≥ k + 1 for every two distinct vertices u and v of G. The value χ k m(c) of a k-metric coloring c is the maximum color assigned by c to a vertex of G and the k-metric chromatic number χ k m(G) of G is the minimum value of a k-metric coloring of G. For every nontrivial connected graph G of order n, χ 1m(G) ≤ χ 2m(G) ≤ . . . ≤ χ n−1 m (G). Metric chromatic numbers provide a generalization of several well-studied coloring parameters in graphs. Upper and lower bounds have been established for χ k m(G) in terms of other graphical parameters of a graph G and exact values of k-metric chromatic numbers have been determined for complete multipartite graphs and cycles. For a nontrivial connected graph G, the anti-diameter adiam(G) is the minimum detour distance between two vertices of G. We show that the adiam(G)-metric chromatic number of a graph G provides information on the Hamiltonian properties of the graph and investigate realization results and problems on this parameter.
For an ordered set W = {w1, w2, . . . , wk} 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 code(v) = (d(v, w1), d(v, w2), . . . , d(v, wk)) where d(v, wi) is the distance between v and wi for 1 6 i 6 k. The set W is a local metric set of G if code(u) 6= code(v) 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 lmd(G) of G. A local metric set of G of cardinality lmd(G) is a local metric basis of G. We characterize all nontrivial connected graphs of order n having local metric dimension 1, n − 2, or n − 1 and establish sharp bounds for the local metric dimension of a graph in terms of well-known graphical parameters. Several realization results are presented along with other results on the number of local metric bases of a connected graph.
A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χm(G) of G. For every graph G, χm(G) is bounded above by its chromatic number χ(G). The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each k ≥ 3, there exist sufficiently large integers n such that χm(C k n) = 3. It is determined for which pairs k, n of integers with 1 ≤ k ≤ n and n ≥ 3, there exists a connected graph G of order n with χm(G) = k. For k = n − 2, all such graphs G are determined.
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.