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 a connected graph G of order n > 2 and a linear ordering s : v1, v2, . . . , vn of vertices of G, d(s) = ∑ nP−1 i=1 d(vi , vi+1), where d(vi , vi+1) is the distance between vi and vi+1. The upper traceable number t +(G) of G is t +(G) = max{d(s)}, where the maximum is taken over all linear orderings s of vertices of G. It is known that if T is a tree of order n ≥ 3, then 2n−3 ≤ t +(T) ≤ ⌊n 2 /2⌋−1 and t +(T) ≤ ⌊n 2 /2⌋−3 if T ≠ Pn. All pairs n, k for which there exists a tree T of order n and t +(T) = k are determined and a characterization of all those trees of order n ≥ 4 with upper traceable number ⌊n 2 /2⌋ − 3 is established. For a connected graph G of order n ≥ 3, it is known that n − 1 ≤ t +(G) ≤ ⌊n 2 /2⌋ − 1. We investigate the problem of determining possible pairs n, k of positive integers that are realizable as the order and upper traceable number of some connected graph.
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, let c : V (G) → N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v ∈ V (G), the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) 6= NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χs(G). We show that the decision variant of determining χs(G) is NP-complete in the general case, and show that χs(G) can be efficiently calculated when G is a threshold graph. We study the difference χ(G) − χs(G), presenting new bounds that are sharp for all graphs G satisfying χ(G) = ω(G). We finally present results of the Nordhaus-Gaddum type, giving sharp bounds on the sum and product of χs(G) and χs(G).
For a nontrivial connected graph $G$, let $c\: V(G)\to \Bbb N$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v$ of $G$, the neighborhood color set ${\rm NC}(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if ${\rm NC}(u)\ne {\rm NC}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number $\chi _s(G)$. A study is made of the set chromatic number of the join $G + H$ of two graphs $G$ and $H$. Sharp lower and upper bounds are established for $\chi _s(G+H)$ in terms of $\chi _s(G)$, $\chi _s(H)$, and the clique numbers $\omega (G)$ and $\omega (H)$.
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.