On the size and complexity of scrambles
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915852434014208 |
|---|---|
| author | Connor, Seamus DiSilvio, Steven Kononova, Sasha Morrison, Ralph Singal, Krish |
| author_facet | Connor, Seamus DiSilvio, Steven Kononova, Sasha Morrison, Ralph Singal, Krish |
| contents | The scramble number of a graph, a natural generalization of bramble number, is an invariant recently developed to study chip-firing games and graph gonality. We introduce the carton number of a graph, defined to be the minimum size of a maximum order scramble, to study the computational complexity of scramble number. We show that there exist graphs with carton number exponential in the size of the graph, proving that scrambles are not valid NP certificates. We characterize families of graphs whose scramble number and gonality can be constant-factor approximated in polynomial time and show that the disjoint version of scramble number is fixed parameter tractable. Lastly, we find that vertex congestion is an upper bound on screewidth and thus scramble number, leading to a new proof of the best known bound on the treewidth of line graphs and a bound on the scramble number of planar graphs with bounded degree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_17342 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the size and complexity of scrambles Connor, Seamus DiSilvio, Steven Kononova, Sasha Morrison, Ralph Singal, Krish Combinatorics 05C57, 05C85, 14T05 The scramble number of a graph, a natural generalization of bramble number, is an invariant recently developed to study chip-firing games and graph gonality. We introduce the carton number of a graph, defined to be the minimum size of a maximum order scramble, to study the computational complexity of scramble number. We show that there exist graphs with carton number exponential in the size of the graph, proving that scrambles are not valid NP certificates. We characterize families of graphs whose scramble number and gonality can be constant-factor approximated in polynomial time and show that the disjoint version of scramble number is fixed parameter tractable. Lastly, we find that vertex congestion is an upper bound on screewidth and thus scramble number, leading to a new proof of the best known bound on the treewidth of line graphs and a bound on the scramble number of planar graphs with bounded degree. |
| title | On the size and complexity of scrambles |
| topic | Combinatorics 05C57, 05C85, 14T05 |
| url | https://arxiv.org/abs/2311.17342 |