主題
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.tw/RadioNumber.html

主題分類