Graphs of scramble number two

DOI10.1016/J.DISC.2023.113539MaRDI QIDQ6172289zbMATH OpenFDO

Authors Robin Eagleton, Ralph Morrison

Publication date 19 July 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.09949

zbMATH Keywords

topological minorsscramble numbergraph gonality

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: The scramble number of a graph provides a lower bound for gonality and an upper bound for treewidth, making it a graph invariant of interest. In this paper we study graphs of scramble number at most two, and give a classification of all such graphs with a finite list of forbidden topological minors. We then prove that there exists no finite list of forbidden topological minors to characterize graphs of any fixed scramble number greater than two.

Recommendations

• A new lower bound on graph gonality
• On the scramble number of graphs
• A note on extremal values of the scattering number
• Scattering number in graphs
• A measure of graph vulnerability: Scattering number

Cites work

• A Reduction Method for Edge-Connectivity in Graphs
• A new lower bound on graph gonality
• Computing graph gonality is hard
• Finding topological subgraphs is fixed-parameter tractable
• On the scramble number of graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph

Cited in

(3)

• Uniform scrambles on graphs
• On the scramble number of graphs
• A new lower bound on graph gonality

This page was built for publication: Graphs of scramble number two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172289)