Zur Seitennavigation oder mit Tastenkombination für den
accesskey
-Taste und Taste 1
Zum Seiteninhalt oder mit Tastenkombination für den
accesskey
und Taste 2
S
tartseite
A
nmelden
Sommer 2024
Hilfe
Sitemap
Impressum
Datenschutz
node2
Studentisches Leben
Veranstaltungen
Einrichtungen
Räume und Gebäude
Personen
Forschung
Startseite
Publikation: Zeitschriftenartikel
Rooted minors and locally spanning subgraphs
Grunddaten
Abstract
Autoren
Einrichtung
Grunddaten
Titel
Rooted minors and locally spanning subgraphs
Erscheinungsjahr
2024
Seiten (von – bis)
209 – 229
Band
105
Heft-Nr.
2
Jahr
2024
Publikationsform
Elektronische Ressource
Publikationsart
Zeitschriftenartikel
Sprache
Englisch
DOI
10.1002/jgt.23012
Letzte Änderung
13.03.2024 17:31:08
Bearbeitungsstatus
durch UB Rostock abschließend validiert
Dauerhafte URL
http://purl.uni-rostock.de/fodb/pub/71324
Links zu Katalogen
Abstract
Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider "local" versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3-connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if G is a planar graph, X is a subset of specified vertices of G such that X cannot be separated in G by removing two or fewer vertices of G, then G has a tree of maximum degree at most 3 containing all vertices of X. Our results constitute a general machinery for strengthening statements about k-connected graphs (for 1 k 4) to locally spanning versions, that is, subgraphs containing a set X V (G) of a (not necessarily planar) graph G in which only X has high connectedness. Given a graph G and X V (G), we say M is a minor of G rooted at X, if M is a minor of G such that each bag of M contains at most one vertex of X and X is a subset of the union of all bags. We show that G has a highly connected minor rooted at X if X V (G) cannot be separated in G by removing a few vertices of G. Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well-known results about degree-bounded trees, Hamiltonian paths and cycles, and 2-connected subgraphs of graphs.
Autoren
Böhme, Thomas
Harant, Jochen
Kriesell, Matthias
Mohr, Samuel
Schmidt, Jens M.
Einrichtung
IEF/IN/IFI/Algorithmen und Komplexität