تسجيل الدخول

تسجيل

Radio Number

المؤلف:  Bantva, D

المصدر:  "Further Results on the Radio Number of Trees." 25 May 2018. https://arxiv.org/abs/1805.10083.

الجزء والصفحة:  ...

8-5-2022

3371

Radio Number

Let  be a finite, connected, undirected graph with graph diameter  and graph distance  between vertices  and . A radio labeling of a graph  is labeling using distinct nonnegative integers such that  for every pair of distinct vertices ,  in the vertex set of . Then the radio number of , commonly denoted , is the smallest integer  such that  has a radio labeling  with {f(v):v in V(G)}=k" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline16.svg" style="height:22px; width:205px" />.

The radio number of path graphs  and cycle graphs  were determined by Liu and Zhu (2005). The following table summarizes some known results for a number of special families of graphs.

graph	radio number
complete graph
complete bipartite graph	{1 for m=n=1; m+n otherwise" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline22.svg" style="height:68px; width:208px" />
complete tripartite graph	{2 for k=m=n=1; k+m+n+1 otherwise" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline24.svg" style="height:68px; width:322px" />
crown graph	for
cycle graph	{(n-2)/2|_n/4_|+n-1 for n=2 (mod 0); ((n-1)(n+3))/8 for n=4 (mod 1); (n-1)/2(2+|_n/4_|) for n=2 (mod 1)" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline28.svg" style="height:116px; width:358px" />
path graph	{0 for n=1; 3 for n=3; 1/2n(n-2)+1 for even n; 1/2(n-3)(n+1)+4 for odd n" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline30.svg" style="height:146px; width:332px" />
star graph	{0 for n=1; 1 for n=2; n otherwise" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline32.svg" style="height:104px; width:130px" />
wheel graph	{3 for n=4; 6 for n=5; n otherwise" src="https://mathworld.wolfram.com/images/equations/RadioNumber/Inline34.svg" style="height:104px; width:130px" />

---

REFERENCES

Bantva, D. "Further Results on the Radio Number of Trees." 25 May 2018. https://arxiv.org/abs/1805.10083.

Chartrand, G.; Erwin, D.; Harary, F.; and Zhang, P. "Radio Labelings of Graphs." Bull. Inst. Combin. Appl. 33, 77-85, 2001.

Chartrand G.; and Zhang, P. "Radio Colorings of Graphs--A Survey." Int. J. Comput. Appl. Math. 2, 237-252, 2007.

Griggs, J. R. and Yeh, R. K. "Labeling Graphs with Condition at Distance. 2." SIAM J. Disc. Math. 5, 586-595, 1992.

Liu, D. "Radio Number for Trees." Disc. Math. 308, 1153-1164, 2008.

Liu, D. D.-F.; Zhu, X. "Multilevel Distance Labelings for Paths and Cycles." SIAM J. Disc. Math. 19, 610-621, 2005.

Zhang, P. "Radio Labeling of Cycles." Ars Combin. 65, 21-32, 2002.