Duality theorems for stars and combs III: Undominated combs

In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs. Here, in the third paper of the series, we present duality theorems for a combination of stars and combs: undominated combs. We describe their complementary...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2022-05, Vol.100 (1), p.127-139
Main Authors: Bürger, Carl, Kurkofka, Jan
Format: Article
Language:English
Subjects:
complementary
dual
duality
Graph theory
Graphs
infinite graph
normal tree
rayless spanning tree
Stars
star‐decomposition
star–comb lemma
Theorems
tree‐decomposition
undominated comb
undominated ends
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:In a series of four papers we determine structures whose existence is dual, in the sense of complementary, to the existence of stars or combs. Here, in the third paper of the series, we present duality theorems for a combination of stars and combs: undominated combs. We describe their complementary structures in terms of rayless trees and of tree‐decompositions. Applications include a complete characterisation, in terms of normal spanning trees, of the graphs whose rays are dominated but which have no rayless spanning tree. Only two such graphs had so far been constructed, by Seymour and Thomas and by Thomassen. As a corollary, we show that graphs with a normal spanning tree have a rayless spanning tree if and only if all their rays are dominated.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22781