Spanning trees of smallest maximum degree in subdivisions of graphs

\newcommand{\subdG}[1][G]{#1^\star} Given a graph \(G\) and a positive integer \(k\), we study the question whether \(G^\star\) has a spanning tree of maximum degree at most \(k\) where \(G^\star\) is the graph that is obtained from \(G\) by subdividing every edge once. Using matroid intersection, w...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-10
Main Authors: Brause, Christoph, Harant, Jochen, Hörsch, Florian, Mohr, Samuel
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Integers
Polynomials
Subdivisions
Tightness
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:\newcommand{\subdG}[1][G]{#1^\star} Given a graph \(G\) and a positive integer \(k\), we study the question whether \(G^\star\) has a spanning tree of maximum degree at most \(k\) where \(G^\star\) is the graph that is obtained from \(G\) by subdividing every edge once. Using matroid intersection, we obtain a polynomial algorithm for this problem and a characterization of its positive instances. We use this characterization to show that \(G^\star\) has a spanning tree of bounded maximum degree if \(G\) is contained in some particular graph class. We study the class of 3-connected graphs which are embeddable in a fixed surface and the class of \((p-1)\)-connected \(K_p\)-minor-free graphs for a fixed integer \(p\). We also give tightness examples for most of these classes.
ISSN:2331-8422