Dual trees must share their ends

DOI10.1016/J.JCTB.2016.11.005zbMATH Open1354.05096arXiv1106.1324OpenAlexW1545645393MaRDI QIDQ505909FDOQ505909

Authors: Reinhard Diestel, Julian Pott 

Publication date: 26 January 2017

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

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.

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

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

zbMATH Keywords

dualityspanning treeinfinite matroidendFreudenthal compactification

Mathematics Subject Classification ID

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

Cites Work

• Planarity and duality of finite and infinite graphs
• Topological paths, cycles and spanning trees in infinite graphs
• Infinite matroids in graphs
• Locally finite graphs with ends: a topological approach. III. Fundamental group and homology
• End spaces and spanning trees
• Duality of infinite graphs
• Duality in Infinite Graphs
• Duality of ends
• Connected but not path-connected subspaces of infinite graphs
• Title not available (Why is that?)

Cited In (7)

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

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)