A different approach for multi-level distance labellings of path structure networks

Main Article Content

Laxman Saha


For a positive integer $k$, a radio $k$-labelling of a simple connected graph $G=(V, E)$ is a mapping $f$ from the vertex set $V(G)$ to a set of non-negative integers such that $|f(u)-f(v)|\geqslant k+1-d(u,v)$ for each pair of distinct vertices $u$ and $v$ of $G$, where $d(u,v)$ is the distance between $u$ and $v$ in $G$. The \emph{span} of a radio $k$-coloring $f$, denoted by $span_f(G)$, is defined as $\displaystyle\max_{v\in V(G)}f(v)$ and the \emph{radio $k$-chromatic number of $G$}, denoted by $rc_k(G)$, is $\displaystyle\min_{f}\{~span_f(G)\}$ where the minimum is taken over all radio $k$-labellings of $G$. In this article, we present results of radio $k$-chromatic number of path $P_n$ for $k\in\{n-1, n-2,n-3\}$ in different approach but simple way.

Article Details

How to Cite
Saha, L. (2024). A different approach for multi-level distance labellings of path structure networks. Tamkang Journal of Mathematics, 55(1), 15–23. https://doi.org/10.5556/j.tkjm.55.2024.3913


Griggs J R, Kral' D (2009) Graph labellings with variable weights, a survey. Discrete Appl. Math. 157: 264-2658 .

Georges J P, Mauro D W, Stein M I (2001) Labelling products of complete graphs with a condition at distance two. SIAM

J. Discrete Math. 14: 28-35.

Griggs J R, Jin X T (2006) Real number graph labelling with distance conditions. SIAM J. Discrete Math. 20: 302-327.

Griggs J R, Yeh R K (1992) Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5: 586-595.

Hale W K (1980) Frequency assignment, theory and application. Proc IEEE 68:1497-1514.

F.S.Roberts, Working group agenda of DIMACS/DIMATIA/Renyi working group on graph colorings and their general-

izations (2003) posted at http://dimacs.rutgers.edu/workshops/GraphColor/main.html.

Chartrand G, Erwin D, Harary F, Zhang P (2001) Radio labelings of graphs. Bull. Inst. Combin. Appl. 33: 77-85.

Chartrand G, Erwin D, Zhang P (2005) A graph labeling problem suggested by FM channel restrictions. Bull. Inst.

Combin. Appl. 43: 43-57.

Chartrand G, Erwin D, Zhang P (2000) Radio antipodal colorings of cycles, Proceedings of the Thirty- 1st Southeastern

International Conference on Combinatorics. Graph Theory and Computing (Boca Raton, FL, 2000) 144: 129-141.

Chartrand G, Nebesky L, Zhang P (2004) Radio k-colorings of paths. Discuss. Math. Graph Theory 24: 5-21.

Khennoufa R, Togni O (2011) The radio antipodal and radio numbers of the hypercube. Ars. Combin. 102: 447-461.

Khennoufa R, Togni O (2005) A note on radio antipodal colourings of paths. Math. Bohem. 130(3): 277-282

Liu D D -F (2008) Radio number for trees. Discrete Math 308: 1153-1164 .

Liu D D -F, Zhu X (2005) Multi-level distance labelings for paths and cycles. SIAM J. Discrete Math. 19: 610-621.

Rao Kola S, Panigrahi P (2009) Nearly antipodal chromatic number ac′(Pn) of the path. Math. Bohem. 134(1): 77-86.

Rao Kola S, Panigrahi P (2009) On radio (n - 4)-chromatic number of the path Pn. AKCE Int. J. Graphs Comb. 6(1): 209-217.