A new lower bound on graph gonality

Michael Harp, Elijah Jackson, David Jensen, Noah Speeter

Research output: Contribution to journalArticlepeer-review

Abstract

We define a new graph invariant called the scramble number. We show that the scramble number of a graph is a lower bound for the gonality and an upper bound for the treewidth. Unlike the treewidth, the scramble number is not minor monotone, but it is subgraph monotone and invariant under subdivision. We compute the scramble number and gonality of several families of graphs for which these invariants are strictly greater than the treewidth.

Original languageEnglish
Pages (from-to)172-179
Number of pages8
JournalDiscrete Applied Mathematics
Volume309
DOIs
StatePublished - Mar 15 2022

Bibliographical note

Funding Information:
This research was conducted as a project with the University of Kentucky Math Lab. The third author was supported by NSF DMS-1601896 . We would like to thank Ralph Morrison for some discussions on this material. We would also like to thank the anonymous referees for several helpful comments, including the suggestion to add Examples 4.8 and 4.9 .

Funding Information:
This research was conducted as a project with the University of Kentucky Math Lab. The third author was supported by NSF DMS-1601896. We would like to thank Ralph Morrison for some discussions on this material. We would also like to thank the anonymous referees for several helpful comments, including the suggestion to add Examples 4.8 and 4.9.

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Chip-firing
  • Gonality
  • Treewidth

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A new lower bound on graph gonality'. Together they form a unique fingerprint.

Cite this