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.
A radio antipodal coloring of a connected graph G with diameter d is an assignment of positive integers to the vertices of G, with x ∈ V (G) assigned c(x), such that d(u, v) + |c(u) − c(v)| ≥ d for every two distinct vertices u, v of G, where d(u, v) is the distance between u and v in G. The radio antipodal coloring number ac(c) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G. The radio antipodal chromatic number ac(G) of G is min{ac(c)} over all radio antipodal colorings c of G. Radio antipodal chromatic numbers of paths are discussed and upper and lower bounds are presented. Furthermore, upper and lower bounds for radio antipodal chromatic numbers of graphs are given in terms of their diameter and other invariants.
Let G be a nontrivial connected graph on which is defined a coloring c : E(G) → {1, 2, . . . , k}, k ∈ N, of the edges of G, where adjacent edges may be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. The graph G is rainbow-connected if G contains a rainbow u − v path for every two vertices u and v of G. The minimum k for which there exists such a k-edge coloring is the rainbow connection number rc(G) of G. If for every pair u, v of distinct vertices, G contains a rainbow u − v geodesic, then G is strongly rainbow-connected. The minimum k for which there exists a k-edge coloring of G that results in a strongly rainbow-connected graph is called the strong rainbow connection number src(G) of G. Thus rc(G) ≤ src(G) for every nontrivial connected graph G. Both rc(G) and src(G) are determined for all complete multipartite graphs G as well as other classes of graphs. For every pair a, b of integers with a ≥ 3 and b ≥ (5a − 6)/3, it is shown that there exists a connected graph G such that rc(G) = a and src(G) = b.
A graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number γF (G) is the minimum number of red vertices in an F-coloring of G. In this paper, we study F-domination where F is a red-blue-blue path of order 3 rooted at a blue end-vertex. It is shown that a triple (A, B, C) of positive integers with A ≤ B ≤ 2A and B ≥ 2 is realizable as the domination number, open domination number, and F-domination number, respectively, for some connected graph if and only if (A, B, C) ≠ (k, k, C) for any integers k and C with C > k ≥ 2.
For an ordered set W = {w1, w2, . . . , wk} 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(v|W) = (d(v, w1), d(v, w2), . . . , d(v, wk)), 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 of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for G is its dimension dim G. A set S of vertices in G is a dominating set for G if every vertex of G that is not in S is adjacent to some vertex of S. The minimum cardinality of a dominating set is the domination number γ(G). A set of vertices of a graph G that is both resolving and dominating is a resolving dominating set. The minimum cardinality of a resolving dominating set is called the resolving domination number γr(G). In this paper, we investigate the relationship among these three parameters.
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 a vertex v of a connected oriented graph D and an ordered set W = [wi, w2,.. •, wk} of vertices of D, Ihe (directed distcince) representation of v with respect to W is the ordered fc-tuple r(v \ W) = (d(v, w1),d(v, w2 ), •.. ,d(v, wk )), where d(v, wi ) is Ihe directed distance from v to wi . 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 dhn(D) of D. The dimension of a connected oriented graph need not be defined. Those oriented graphs with dimension 1 are characterized. We discuss the problem of determining the largest dimension of an oriented graph with a fixed order. It is shown that if the outdegree of every vertex of a connected oriented graph D of order n is at least 2 and dim(D) is defined, then dim(D) ≤ n - 3 and this bound is sharp.
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(S)$. A set $S$ is a convex set if $I(S) = S$. The convexity number $\mathop {\mathrm con}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop {\mathrm con}(G)$ 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 containing $T$. The forcing convexity number $f(S, \mathop {\mathrm con})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop {\mathrm con})$ of $G$ is the minimum forcing convexity number among all maximum convex sets of $G$. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph $G$, $f(G, \mathop {\mathrm con}) \le \mathop {\mathrm con}(G)$. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ and $b \ge 3$ is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of $H \times K_2$ for a nontrivial connected graph $H$ is studied.