主题
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 数

使用 Wolfram|Alpha 探索

参考文献

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." 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/Gonality.html

主题分类