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.
@article{10_37236_9307,
author = {Ivan Aidun and Ralph Morrison},
title = {On the gonality of {Cartesian} products of graphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9307},
zbl = {1466.05223},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9307/}
}
TY - JOUR
AU - Ivan Aidun
AU - Ralph Morrison
TI - On the gonality of Cartesian products of graphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9307/
DO - 10.37236/9307
ID - 10_37236_9307
ER -
%0 Journal Article
%A Ivan Aidun
%A Ralph Morrison
%T On the gonality of Cartesian products of graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9307/
%R 10.37236/9307
%F 10_37236_9307
Ivan Aidun; Ralph Morrison. On the gonality of Cartesian products of graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9307
