Duality theorems for stars and combs II: Dominating stars and dominated combs

DOI10.1002/JGT.22757MaRDI QIDQ6057656zbMATH OpenOpenAlexWikidataFDO

Authors Carl Bürger, Jan Kurkofka

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/2004.00593

zbMATH Keywords

dominated combdominating stardualitynormal treestar-comb lemmatree-decomposition

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: 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 second paper of the series, we present duality theorems for combinations of stars and combs: dominating stars and dominated combs. As dominating stars exist if and only if dominated combs do, the structures complementary to them coincide. Like for arbitrary stars and combs, our duality theorems for dominated combs (and dominating stars) are phrased in terms of normal trees or tree-decompositions. The complementary structures we provide for dominated combs unify those for stars and combs and allow us to derive our duality theorems for stars and combs from those for dominated combs. This is surprising given that our complementary structures for stars and combs are quite different: those for stars are locally finite whereas those for combs are rayless.

Recommendations

• Duality theorems for stars and combs III: Undominated combs
• Duality in Infinite Graphs
• Duality theorems for stars and combs I: Arbitrary stars and combs
• Duality theorems for blocks and tangles in graphs
• Duality theorems for stars and combs IV: Undominating stars

Cites work

• All graphs have tree-decompositions displaying their topological ends
• End spaces and spanning trees
• Simplicial Decompositions of Infinite Graphs
• Wurzelbäume und unendliche Wege in Graphen

Cited in

(7)

• A tree-of-tangles theorem for infinite tangles
• End spaces and tree-decompositions
• Duality theorems for stars and combs III: Undominated combs
• Duality theorems for stars and combs IV: Undominating stars
• Duality theorems for stars and combs I: Arbitrary stars and combs
• End‐faithful spanning trees in graphs without normal spanning trees
• A representation theorem for end spaces of infinite graphs

This page was built for publication: Duality theorems for stars and combs II: Dominating stars and dominated combs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057656)