Blockers for non-crossing spanning trees in complete geometric graphs

Details Blockers for non-crossing spanning trees in complete geometric graphs Blockers for non-crossing spanning trees in complete geometric graphs

2012-01-23

arxiv.org/abs/1201.4782v1

Mathematics

Combinatorics

14 pages, 10 figures, to appear in the book "Thirty Essays in Geometric Graph Theory" edited by J. Pach

Scientific paper

In this paper we present a complete characterization of the smallest sets that block all the simple spanning trees (SSTs) in a complete geometric graph. We also show that if a subgraph is a blocker for all SSTs of diameter at most 4, then it must block all simple spanning subgraphs, and in particular, all SSTs. For convex geometric graphs, we obtain an even stronger result: being a blocker for all SSTs of diameter at most 3 is already sufficient for blocking all simple spanning subgraphs.

Affiliated with

Also associated with

No associations

Rating

Blockers for non-crossing spanning trees in complete geometric graphs 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 Blockers for non-crossing spanning trees in complete geometric graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Blockers for non-crossing spanning trees in complete geometric graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498199