主题
数学天地
Search

无线电数

下载 Mathematica Notebook下载 Wolfram Notebook

设 G 是一个有限的、连通的、无向图，其图直径为 d(G)，图距离 d(u,v) 表示顶点 u 和 v 之间的距离。图 G 的无线电标记是使用不同的非负整数进行标记，使得对于每对不同的顶点 u, v 在 G 的顶点集中，满足 |f(u)-f(v)|>=d(G)+1-d(u,v)。那么，图 G 的无线电数，通常表示为 rn(G)，是最小的整数 k，使得图 G 存在无线电标记 f，且 max{f(v):v in V(G)}=k。

路径图 P_n 和 圈图 C_n 的无线电数由 Liu 和 Zhu (2005) 确定。下表总结了一些特殊图族的已知结果。

图无线电数
完全图 K_nn-1
完全二部图 K_(m,n){1 for m=n=1; m+n otherwise
完全三部图 K_(k,m,n){2 for k=m=n=1; k+m+n+1 otherwise
冠图3n-2 对于 n>1
圈图 C_n{(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)
路径图 P_n{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
星图 S_n{0 for n=1; 1 for n=2; n otherwise
轮图 W_n{3 for n=4; 6 for n=5; n otherwise

另请参阅

图直径, 图距离

使用 探索

参考文献

Bantva, D. "关于树的无线电数的进一步结果。" 2018 年 5 月 25 日。 https://arxiv.org/abs/1805.10083.Chartrand, G.; Erwin, D.; Harary, F.; and Zhang, P. "图的无线电标记。" 组合应用研究所公报 33, 77-85, 2001.Chartrand G.; and Zhang, P. "图的无线电着色--综述。" 国际计算与应用数学杂志 2, 237-252, 2007.Griggs, J. R. and Yeh, R. K. "图的距离条件标记。2。" SIAM 离散数学杂志 5, 586-595, 1992.Liu, D. "树的无线电数。" 离散数学 308, 1153-1164, 2008.Liu, D. D.-F.; Zhu, X. "路径和圈的多层距离标记。" SIAM 离散数学杂志 19, 610-621, 2005.Zhang, P. "圈的无线电标记。" 组合学 65, 21-32, 2002.

请引用为

Weisstein, Eric W. "无线电数。" 出自 Web 资源。 https://mathworld.net.cn/RadioNumber.html

主题分类