Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 45 min ago
PreprintarXiv licencearXiv

The scramble number of outerplanar graphs

  • Doel Rivera Laboy
Open at sourcePDFDOICite

Abstract

For planar graphs, it is known that their treewidth is bounded by O(√n), where n is the number of vertices of the graph. A related invariant to treewidth, is the scramble number of graphs. Recently, Connor et. al proved that planar graphs of bounded maximal degree have scramble number bounded by O(√n). An open question is whether the scramble number of any planar graph follows this same bound. We give a definitive answer with an explicit bound for a subset of planar graphs, the simple outerplanar graphs and the simple near outerplanar graphs.

Related

  1. An improved upper bound for the fair domination number of maximal outerplanar graphs
    Yair Caro, Riste Škrekovski
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Bounds for B-coloring planar and outerplanar graphs
    Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
    Discrete MathematicsPeer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
  3. Bounds for B-coloring planar and outerplanar graphs
    Ryan R. Martin, Miklós Ruszinkó, Gábor N. Sárközy
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Extremal spectral result of outerplanar graphs without P3· l
    Fulong Ye, Yuxiang Liu, Ligong Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair
    Zongjian Han, Yiran Liang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{laboy2026scramble,
  title = {{The scramble number of outerplanar graphs}},
  author = {Doel Rivera Laboy},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.03755},
  eprint = {2609.03755},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.03755},
}
RIS
TY  - UNPB
TI  - The scramble number of outerplanar graphs
AU  - Doel Rivera Laboy
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.03755
UR  - https://arxiv.org/abs/2609.03755
AB  - For planar graphs, it is known that their treewidth is bounded by O(√n), where n is the number of vertices of the graph. A related invariant to treewidth, is the scramble number of graphs. Recently, Connor et. al proved that planar graphs of bounded maximal degree have scramble number bounded by O(√n). An open question is whether the scramble number of any planar graph follows this same bound. We give a definitive answer with an explicit bound for a subset of planar graphs, the simple outerplanar graphs and the simple near outerplanar graphs.
ER  -