Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
radio $k$-coloring; span; radio $k$-chromatic number
radio $k$-coloring; span; radio $k$-chromatic number
Summary:
Chartrand et al.\ (2004) have given an upper bound for the nearly antipodal chromatic number $ac'(P_n)$ as $\binom {n-2}2+2$ for $n \geq 9$ and have found the exact value of $ac'(P_n)$ for $n=5,6,7,8$. Here we determine the exact values of $ac'(P_n)$ for $n \geq 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(P_n)$ 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(P_n)$ determined there is correct, we found a mistake in the proof of the lower bound when $n=2p$ (Theorem $6$). However, we give an easy observation which proves this lower bound.
References:
[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs. Bull. Inst. Combin. Appl. 33 (2001), 77-85. MR 1913399 | Zbl 0989.05102
[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of cycles. Congr. Numerantium 144 (2000), 129-141. MR 1817928 | Zbl 0976.05028
[3] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs. Math. Bohem. 127 (2002), 57-69. MR 1895247 | Zbl 0995.05056
[4] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths. Discuss. Math., Graph Theory 24 (2004), 5-21. DOI 10.7151/dmgt.1209 | MR 2118291 | Zbl 1056.05053
[5] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohem. 130 (2005), 277-282. MR 2164657 | Zbl 1110.05033
[6] Liu, D., Zhu, X.: Multi-level distance labelings for paths and cycles. SIAM J. Discrete Math. 19 (2005), 610-621. DOI 10.1137/S0895480102417768 | MR 2191283
[7] Mustapha Kchikech, Riadh Khennoufa, Olivier Togni: Linear and cyclic radio $k$-labelings of trees. Discuss. Math., Graph Theory 27 (2007), 105-123. DOI 10.7151/dmgt.1348 | MR 2321426
Search
Partner of
