On the Gonality of Cartesian Products of Graphs
On the Gonality of Cartesian Products of Graphs
复制标题
论图的笛卡尔积的Goality
DOI：
10.37236/9307
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ralph Morrison
中科院分区：
文献类型：
--
作者：
Ivan Aidun;Ralph Morrison
本文首次系统地讨论了图的笛卡尔乘积及其除数正交性，它是用切片法定义的一条代数曲线的正交性的热带版本。我们证明了任意两个图的笛卡尔乘积的正交性的一个上界，并确定了这个上界相等的例子，包括$m次n$rook图的$\minm，n\leq5$。我们用我们的上界证明了Baker的正规性猜想对任意两个有两个或两个以上顶点的图的笛卡尔积成立。我们精确地确定了哪些非平凡乘积图的阶数等于Baker猜想的上界。我们还将我们的一些结果推广到度量图上。
In this paper we provide the first systematic treatment of Cartesian products of graphs and their divisorial gonality, which is a tropical version of the gonality of an algebraic curve defined in terms of chip-firing. We prove an upper bound on the gonality of the Cartesian product of any two graphs, and determine instances where this bound holds with equality, including for the $m\times n$ rook's graph with $\min\{m,n\}\leq 5$. We use our upper bound to prove that Baker's gonality conjecture holds for the Cartesian product of any two graphs with two or more vertices each, and we determine precisely which nontrivial product graphs have gonality equal to Baker's conjectural upper bound. We also extend some of our results to metric graphs.