Dual trees must share their ends

DOI10.1016/J.JCTB.2016.11.005MaRDI QIDQ505909zbMATHOpenAlexFDO

Authors Reinhard Diestel, Julian Pott

Publication date 26 January 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

dualityspanning treeinfinite matroidendFreudenthal compactification

Mathematics Subject Classification ID

Trees (05C05) Combinatorial aspects of matroids and geometric lattices (05B35) Infinite graphs (05C63)

Abstract: We extend to infinite graphs the matroidal characterization of finite graph duality, that two graphs are dual iff they have complementary spanning trees in some common edge set. The naive infinite analogue of this fails. The key in an infinite setting is that dual trees must share between them not only the edges of their host graphs but also their ends: the statement that a set of edges is acyclic and connects all the vertices in one of the graphs iff the remaining edges do the same in its dual will hold only once each of the two graphs' common ends has been assigned to one graph but not the other, and 'cycle' and 'connected' are interpreted topologically in the space containing the respective edges and precisely the ends thus assigned. This property characterizes graph duality: if, conversely, the spanning trees of two infinite graphs are complementary in this end-sharing way, the graphs form a dual pair.

Recommendations

• Duality of ends
• Topological paths, cycles and spanning trees in infinite graphs
• Duality in Infinite Graphs
• On infinite cycles. I, II
• Infinite matroids in graphs

Cites work

• scientific article; zbMATH DE number 3114861 (Why is no real title available?)
• Connected but not path-connected subspaces of infinite graphs
• Duality in Infinite Graphs
• Duality of ends
• Duality of infinite graphs
• End spaces and spanning trees
• Infinite matroids in graphs
• Locally finite graphs with ends: a topological approach. III. Fundamental group and homology
• Planarity and duality of finite and infinite graphs
• Topological paths, cycles and spanning trees in infinite graphs

Cited in

(7)

• Duality theorems for stars and combs I: Arbitrary stars and combs
• On the intersection conjecture for infinite trees of matroids
• Duality of ends
• End spaces and tree-decompositions
• Paired bondage in trees
• Labeled trees generating complete, compact, and discrete ultrametric spaces
• Axioms for infinite matroids

This page was built for publication: Dual trees must share their ends

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