Multiplicity-Free Gonality on Graphs

The divisorial gonality of a graph is the minimum degree of a positive rank divisor on that graph. We introduce the multiplicity-free gonality of a graph, which restricts our consideration to divisors that place at most \(1\) chip on each vertex. We give a sufficient condition in terms of vertex-con...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-07
Main Authors: Dean, Frances, Everett, Max, Morrison, Ralph
Format: Article
Language:English
Subjects:
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The divisorial gonality of a graph is the minimum degree of a positive rank divisor on that graph. We introduce the multiplicity-free gonality of a graph, which restricts our consideration to divisors that place at most \(1\) chip on each vertex. We give a sufficient condition in terms of vertex-connectivity for these two versions of gonality to be equal; and we show that no function of gonality can bound multiplicity-free gonality, even for simple graphs. We also prove that multiplicity-free gonality is NP-hard to compute, while still determining it for graph families for which gonality is currently unknown. We also present new gonalities, such as for the wheel graphs.
ISSN:2331-8422