Let G be a simple connected graph. For any two vertices u and v, let d(u,v) denote the distance between u and v in G, and let diam(G) denote the diameter of G. A radio-labeling of G is a function f which assigns to each vertex a non-negative integer (label) such that for every distinct vertices u and v in G, it holds that |f(u)−f(v)|≥diam(G)−d(u,v)+1. The span of f is the difference between the largest and smallest labels of f(V). The radio number of G, denoted by rn(G), is the smallest span of a radio labeling admitted by G. In this paper, we give a lower bound for the radio number of the Cartesian product of two trees. Moreover, we present three necessary and sufficient conditions, and three sufficient conditions for the product of two trees to achieve this bound. Applying these results, we determine the radio number of the Cartesian product of two stars as well as a path and a star.

Let G(V,E) be a simple graph with m edges. For a given integer k, a k-shifted antimagic labeling is a bijection f:E(G)→{k+1,k+2,…,k+m} such that all vertices have different vertex-sums, where the vertex-sum of a vertex v is the total of the labels assigned to the edges incident to v. A graph G is {\it k-shifted antimagic} if it admits a k-shifted antimagic labeling. For the special case when k=0, a 0-shifted antimagic labeling is known as {\it antimagic labeling}; and G is {\it antimagic} if it admits an antimagic labeling. A spider is a tree with exactly one vertex of degree greater than two. A spider forest is a graph where each component is a spider. In this article, we prove that certain spider forests are k-shifted antimagic for all k≥0. In addition, we show that for a spider forest G with m edges, there exists a positive integer k0

Let G be a simple connected graph. For any two vertices u and v, let d(u,v) denote the distance between u and v in G. A radio-k-labeling of G for a fixed positive integer k is a function f which assigns to each vertex a non-negative integer label such that for every two vertices u and v in G, |f(u)−f(v)|⩾k−d(u,v)+1. The span of f is the difference between the largest and smallest labels of f(V). The radio-k-number of a graph G, denoted by rnk(G), is the smallest span among all radio-k-labelings admitted by G. A cycle Cn has diameter d=⌊n/2⌋. In this paper, we combine a lower bound approach with cyclic group structure to determine the value of rnk(Cn) for k⩾n−3. For d⩽k

A radio labeling of a graph G is a mapping f : V ( G ) → {0, 1, 2,...} such that | f ( u ) − f ( v ) | ⩾ d ( G ) + 1 − d ( u , v ) holds for every pair of vertices u and v , where d ( G ) is the diameter of G and d ( u , v ) is the distance between u and v in G . The radio number of G , denoted by r n ( G ) , is the smallest t such that G admits a radio labeling with t = max ⁡ { | f ( v ) − f ( u ) | : v , u ∈ V ( G ) } . A block graph is a graph such that each block (induced maximal 2-connected subgraph) is a complete graph. In this paper, a lower bound for the radio number of block graphs is established. The block graph which achieves this bound is called a lower bound block graph . We prove three necessary and sufficient conditions for lower bound block graphs. Moreover, we give three sufficient conditions for a graph to be a lower bound block graph. Using these results, we present several families of lower bound block graphs, including the level-wise regular block graphs and the extended star of blocks. The line graph of a graph G ( V , E ) has E ( G ) as the vertex set, where two vertices are adjacent if they are incident edges in G . We extend our results to trees as trees and its line graphs are block graphs. We prove that if a tree is a lower bound block graph then, under certain conditions, its line graph is also a lower bound block graph, and vice versa. Consequently, we show that the line graphs of many known lower bound trees, excluding paths, are lower bound block graphs.

Let G be a graph. A circular distance two labeling with span k is a function $f: V(G) \to \{0, 1, 2, \ldots, k-1\}$ such that (1) $2 \leq |f(u)-f(v)| \leq k-2$ if u and v are adjacent and (2) $f(u) \neq f(v)$ if u and v are of distance two apart. We denote by $\lambda_c(G)$ the smallest span of a circular distance two labeling for G. Let $\Delta(G)$ be the maximum degree of G. We prove, for any outerplanar graph G with $\Delta(G) \geq 15$, $\lambda_c(G)=\Delta(G) +3$. It is also shown that there exist outerplanar graphs G with $\Delta(G) = 2, 3, 4, 5$ for which $\lambda_c(G) = \Delta(G) +4$. Moreover, we prove that $\lambda_c(G) \leq \Delta(G) +5$ for any triangulated outerplanar graph, $\lambda_c(G) \leq \Delta(G) +7$ for any outerplanar graph, and $\lambda_c(G) \leq \Delta(G) +4$ for any outerplanar graph with $\Delta(G) \geq 11$. Immediate consequences of our results include that $\lambda(G) \leq \Delta(G) + 2$ for any outerplanar graphs with $\Delta(G) \geq 15$, where $\lambda(G)$ is the minimum k of a k-L(2, 1)-labeling (or distance two labeling) for G.

For a graph G, let $\diam(G)$ denote the diameter of G. For any two vertices u and v in G, let $d(u, v)$ denote the distance between u and v. A multilevel distance labeling (or distance labeling) for G is a function f that assigns to each vertex of G a nonnegative integer such that for any vertices u and v, $|f(u)-f(v)| \geq \diam(G) - d_G(u, v) +1$. The span of f is the largest number in $f(V)$. The radio number of G, denoted by $rn(G)$, is the minimum span of a distance labeling for G. In this paper, we completely determine the radio numbers for paths and cycles.

Given a nonnegative integer r, a no-hole (r+1)-distant coloring, called $\hbox{N}_{r}$-coloring, of a graph G is a function that assigns a nonnegative integer (color) to each vertex such that the separation of the colors of any pair of adjacent vertices is greater than r,, and the set of the colors used must be consecutive. Given r and G, the minimum N r -span of G, nsp r (G), is the minimum difference of the largest and the smallest colors used in an N r -coloring of G if there exists one; otherwise, define ${\rm nsp}_r(G)=\infty$. The values of nsp 1 (G) (r=1) for bipartite graphs are given by Roberts [Math. Comput. Modelling, 17 (1993), pp. 139--144]. Given $r \geq 2$, we determine the values of nsp r (G) for all bipartite graph with at least r-2 isolated vertices. This leads to complete solutions of nsp 2 (G) for bipartite graphs.

A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number (also known as the star chromatic number). We prove that members of a certain family of circulant graphs are star extremal. The result generalizes some known theorems of Sidorenko [Discrete Math., 91 (1991), pp. 215--217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147--156]. We show relations between circulant graphs and distance graphs and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330--339] on asymptotic independence ratios of circulant graphs.