主題
Search

Gonality


Gonality(也稱為除子gonality) gon(G) of a (finite) graph G 是該圖上秩為 1 的除子的最小度數。它可以被認為是放置在該圖上的最小晶片數,這樣透過在所有可能的債務放置上的“晶片移動”可以消除 1 的債務。圖gonality 由 Baker 和 Norine (2007, 2009) 引入,類似於代數曲線上的除子理論。

圖的 gonality 是代數曲線 gonality 的幾種圖類似物之一,代數曲線 gonality 是從曲線到射影線的有理對映的最小度數 (Echavarria 2021)。

圖的 gonality 滿足

 kappa(G)<=lambda(G)<=tw(G)<=sn(G)<=gon(G),

其中 kappa(G)頂點連通度, lambda(G)邊連通度, tw(G)樹寬, 並且 sn(G)scramble 數 of G (Harp et al. 2020, Echavarria et al. 2021)。

樹的 gonality 為 1。Echavarria et al. (2021, 示例 2.7 和 2.8) 總結了許多特殊圖類的 gonalities。

圖的 gonality 是 NP-hard 問題,難以計算 (Gijswijt et al. 2020, Echavarria 2021)。


另請參閱

Scramble 數

使用 探索

參考文獻

Baker, M. and Norine, S. "Riemann-Roch and Abel-Jacobi Theory on a Finite Graph." Adv. Math. 215, 766-788, 2007.Baker, M. and Norine, S. "Harmonic Morphisms and Hyperelliptic Graphs." Int. Math Res. Not. 1, 2914-2955, 2009.Echavarria, M.; Everett, M.; Huang, R.; Jacoby, L.; Morrison, R.; Weber, B. "On the Scramble Number of Graphs." 29 Mar 2021. https://arxiv.org/abs/2103.15253.Gijswijt, D.; Smit, H.; and van der Wegen, M. "Computing Graph Gonality Is Hard." Disc. Appl. Math. 287, 134-149, 2020.Harp, M.; Jackson, E.; Jensen, D.; and Speeter, N. "A New Lower Bound on Graph Gonality." 1 Jun 2020. https://arxiv.org/abs/2006.01020.Morrison, R. and Tolley, L. "Computing Higher Graph Gonality Is Hard." 6 Aug 2022. https://arxiv.org/abs/2208.03573.

引用為

Weisstein, Eric W. "Gonality." 來自 網路資源。 https://mathworld.tw/Gonality.html

主題分類