Graphs of scramble number two

DOI10.1016/J.DISC.2023.113539zbMATH Open1518.05136arXiv2212.09949MaRDI QIDQ6172289FDOQ6172289

Authors: Robin Eagleton, Ralph Morrison 

Publication date: 19 July 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)