主題
Search

不規則強度

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

考慮一個沒有孤立邊且至多有一個孤立點的簡單圖。給每條邊分配一個正整數權重 1<=w_(ij)<=k，並將相應的頂點標籤 w_i 定義為等於與 v_i 關聯的邊的權重之和。那麼圖 G 的不規則強度 s(G) (也表示為 I(G)，例如，Dinitz et al. 1992)，是使得頂點權重全部不同的最小的 k 值 (Chartrand et al. 1988, Przybylo 2024)。

對於具有一個或多個孤立邊或多於一個孤立點的圖，定義 s(G)=infty。

對於任何圖 G，除了具有有限不規則強度的 n 個頂點的三角形圖之外，

s(G)<=n-1
(1)

(Nierhoff 2000, Przybylo 2024)，對於 n>2 的星圖 S_n 等式成立 (Przybylo 2024)。

對於 n>=3 個頂點的連通圖，Chartrand et al. (1988) 給出了下界

s(G)<=max_(1<=i<=Delta)(n_i+i-1)/i,
(2)

其中 n_i 是頂點度為 i 的頂點數，Delta 是 G 的最大頂點度。對於度為 d 的正則圖，此條件簡化為

s(G)>=(n+d-1)/d
(3)

(Przybylo 2024)。雅各布森和萊赫爾提出的另一個界限定義了

lambda(G)=max_(1<=i<=j)((sum_(k=i)^(j)n_k)+i-1)/j,
(4)

那麼

s(G)>=lambda(G),
(5)

(Ebert et al. 1990, Dinitz et al. 1992, Bohman 和 Kravitz 2004)。請注意，一些作者 (例如，Ebert et al. 1990, Bohman 和 Kravtiz 2004) 將 lambda(G) 保留為上面定義的潛在有理數，而另一些作者 (例如，Dinitz et al. 1992) 顯式地在右側添加了上限函式以使其成為整數。

對於最小頂點度 delta>0 的圖，

s(G)<=6[n/delta]
(6)

(Kalkowski et al. 2011, Przybylo 2024)。

Faudree 和 Lehel (1987) 推測存在一個絕對常數 C，使得對於每個具有 n 個頂點和 d>=2 的 d-正則圖 G，

s(G)<=n/d+C
(7)

(Przybylo 2024)。

另請參閱

不規則圖, 正則圖

使用 探索

參考資料

Amar, D. "大度正則圖的不規則強度。" Disc. Math. 114, 9-17, 1993.Anholcer, M. 和 Palmer, C. "迴圈圖的不規則標記。" Discr. Math. 312, 3461-3466, 2012.Bača, M.; Imran, M.; 和 Semaničová-Feňovč’ková', A. "輪圖的不規則性和模不規則強度。" Mathematics 9, 2710, 2021.Bohman, T. 和 Kravitz, D. "關於樹的不規則強度。" J. Graph Th. 45, 241-254, 2004.Chartrand, G.; Jacobson, M. S.; Lehel, J.; Oellermann, O. R.; Ruiz, S.; 和 Saba, F. "不規則網路。" Congr. Numer. 64, 197-210, 1988.Dinitz, J. H.; Garnick, D. K.; 和 Gyárfás, A. "關於 m×n 網格的不規則強度。" J. Graph Th. 16, 355-374, 1992.Ebert, G., Hemmeter, J.; Lazebnik F.; 和 Woldar, A. "關於圖上不規則賦值的數量。" Disc. Math. 93, 141-142, 1991.Ebert, G.; Hammenter, J.; Lazebnik, F.; 和 Woldar, A. "某些圖的不規則強度。" Congr. Numer. 71, 39-52, 1990.Faudree, R.; Schelp, R.; Jacobson, M.; 和 Lehel, J. "不規則網路、正則圖和具有不同行和列和的整數矩陣。" Disc. Math. 76, 223-240, 1989.Faudree, R. J. 和 Lehel, J. "正則圖的不規則強度的界。" In Colloq. Math. Soc. Janós Bolyai, Vol. 52, Combinatorics, Eger. Amsterdam, Netherlands: North-Holland, pp. 247-256, 1987.Gallian, J. §7.13 in "圖示記的動態調查。" Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gyarfas, A. "K_(m,m) 的不規則強度對於 m 奇數時為 4。" Discr. Math. 71, 273-274, 1988.Jacobson, M. S. 和 Lehel, J. "不規則網路強度的界。" Preprint.Jendroľ, S. 和 Tkác, M. "tK_p 的不規則強度。" Disc. Math. 145, 301-305, 1995.Jendrol', S. 和 Žoldák, V. "廣義彼得森圖的不規則強度。" Math. Slovaca 45, 107-113, 1995.Jinnah, M. I. 和 Santhosh Kumar, K. R. "三角形蛇和雙三角形蛇的不規則強度。" Adv. Appl. Disc. Math. 9, 83-92, 2012.Kalkowski, M.; Karoński, M.; 和 Pfender, F. "圖的不規則強度的新上限。" SIAM J. Disc. Math. 25, 1319-1321, 2011.Lehel, J. "關於度不規則賦值的事實和探索。" In Graph Theory, Combinatorics and Applications: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University (Ed. Y. Alavi, F. R. K. Chung, R. L. Graham, 和 D. F. Hsu). New York: Wiley, pp 765-782 1991.Nierhoff, T. "圖的不規則強度的緊界。" SIAM J. Disc. Math. 13, 313-323, 2000.Przybylo, J. "稠密圖的不規則強度——關於 Faudree、Jacobson、Kinch 和 Lehel 問題的漸近最優解。" 13 Jun 2024. https://arxiv.org/abs/2406.09584.

引用為

Weisstein, Eric W. "不規則強度。" 來自 Web 資源。 https://mathworld.tw/IrregularityStrength.html