A new lower bound on graph gonality

Michael Harp; Elijah Jackson; David Jensen; Noah Speeter

doi:10.1016/j.dam.2021.11.003

A new lower bound on graph gonality

Michael Harp, Elijah Jackson, David Jensen, Noah Speeter

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	172-179
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	309
DOIs	https://doi.org/10.1016/j.dam.2021.11.003
State	Published - 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

Access to Document

10.1016/j.dam.2021.11.003

Cite this

@article{cbb6787fd63949b287d82808316429f1,

title = "A new lower bound on graph gonality",

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.",

keywords = "Chip-firing, Gonality, Treewidth",

author = "Michael Harp and Elijah Jackson and David Jensen and Noah Speeter",

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: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = mar,

day = "15",

doi = "10.1016/j.dam.2021.11.003",

language = "English",

volume = "309",

pages = "172--179",

}

TY - JOUR

T1 - A new lower bound on graph gonality

AU - Harp, Michael

AU - Jackson, Elijah

AU - Jensen, David

AU - Speeter, Noah

N1 - 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.

PY - 2022/3/15

Y1 - 2022/3/15

N2 - 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.

AB - 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.

KW - Chip-firing

KW - Gonality

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85120946138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85120946138&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.11.003

DO - 10.1016/j.dam.2021.11.003

M3 - Article

AN - SCOPUS:85120946138

VL - 309

SP - 172

EP - 179

ER -

A new lower bound on graph gonality

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this