Dual trees must share their ends

Details Dual trees must share their ends Dual trees must share their ends

2011-06-07

arxiv.org/abs/1106.1324v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dual trees must share their ends does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dual trees must share their ends, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dual trees must share their ends will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26500