论文标题
较高图的界限
Bounds on higher graph gonality
论文作者
论文摘要
我们证明了有限图的较高性质上的新下限和上限。这些界限是对较高性高的概述的已知上限和下限的概括，包括涉及独立数量的高态性上的上限，以及cramble数字上的高态性。我们应用界限来研究计算较高的高态性的计算复杂性，证明在限制到无数次的分隔线时，计算图形的第二个gonation是NP-HARD。
We prove new lower and upper bounds on the higher gonalities of finite graphs. These bounds are generalizations of known upper and lower bounds for first gonality to higher gonalities, including upper bounds on gonality involving independence number, and lower bounds on gonality by scramble number. We apply our bounds to study the computational complexity of computing higher gonalities, proving that it is NP-hard to compute the second gonality of a graph when restricting to multiplicity-free divisors.
