Advanced Search

An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring f : V (G) → Z+ ∪ {0} such that |f(u) − f(v)| ≥ 2 for all edges uv of G, and |f(u)−f(v)| ≥ 1 if d(u, v) = 2, where d(u, v) is the distance between vertices u and v in G. The span of an L(2, 1)-coloring is the maximum color (or label) assigned by it. The span of a graph G is the smallest integer λ such that there exists an L(2, 1)-coloring of G with span λ. An L(2, 1)-coloring of a graph with span equal to the span of the graph is...

We observe that a lobster with diameter at least five has a unique path $H=x_0,x_1,...,x_m$ with the property that besides the adjacencies in $H$ both $x_0$ and $x_m$ are adjacent to the centers of at least one $K_{1,s}$, where $s>0$, and each $x_i$, $1\le i\le m-1$, is adjacent at most to the centers of some $K_{1,s}$, where $s\ge 0$. This path $H$ is called the central path of the lobster. We call $K_{1,s}$ an even branch if $s$ is nonzero even, an odd branch if $s$ is odd and a pendant branch if $s=0$. In the existing literature only some specific classes of lobsters have been found...

Chartrand et al. (2004) have given an upper bound for the nearly antipodal chromatic number $a{c}^{\text{'}}\left(P_n\right)$ as $\left(\genfrac{}{}{0pt}{}{n-2}{2}\right)+2$ for $n\ge 9$ and have found the exact value of $a{c}^{\text{'}}\left(P_n\right)$ for $n=5,6,7,8$. Here we determine the exact values of $a{c}^{\text{'}}\left(P_n\right)$ for $n\ge 8$. They are $2p^2-6p+8$ for $n=2p$ and $2p^2-4p+6$ for $n=2p+1$. The exact value of the radio antipodal number $ac\left(P_n\right)$ for the path $P_n$ of order $n$ has been determined by Khennoufa and Togni in 2005 as $2p^2-2p+3$ for $n=2p+1$ and $2p^2-4p+5$ for $n=2p$. Although the value of $ac\left(P_n\right)$ determined there is correct, we found a mistake in the proof of the lower bound when $n=2p$ (Theorem $6$). However,...