Treewidth and gonality of glued grid graphs

We compute the treewidth of a family of graphs we refer to as the glued grids, consisting of the stacked prism graphs and the toroidal grids. Our main technique is constructing strict brambles of large orders. We discuss connections to divisorial graph theory coming from tropical geometry, and use o...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-05, Vol.279, p.1-11
Main Authors: Aidun, Ivan, Dean, Frances, Morrison, Ralph, Yu, Teresa, Yuan, Julie
Format: Article
Language:English
Subjects:
Brambles
Gonality
Graph
Graph theory
Graphs
Stacked prism
Toroidal grid
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We compute the treewidth of a family of graphs we refer to as the glued grids, consisting of the stacked prism graphs and the toroidal grids. Our main technique is constructing strict brambles of large orders. We discuss connections to divisorial graph theory coming from tropical geometry, and use our results to compute the divisorial gonality of these graphs.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2019.10.024