```
Bar-Ilan Combinatorics Seminar

The next meeting of the seminar will take place, IYH,

(when)  Sunday, 30 Nisan (Apr. 22), 14:00-15:30

(where) Room 201 (Math & CS Seminar Room), Building 216,
Bar-Ilan University

(who)    Chaya Keller (Hebrew University)

(what)   Simple spanning trees in geometric graphs

Note: The talk will be given in Hebrew.

Abstract:

For a set P of points in the plane, the Simple Spanning Tree (SST) graph
on P, denoted by G(P), is a graph whose "vertices" are simple (i.e.,
non-crossing) trees whose set of vertices is P, such that two trees are
connected by an "edge" if their symmetric difference contains only two
edges.

In this talk we would like to characterize the center of G(P). It turns
out that the center of G(P) is related to the notion of a blocker for
SSTs, defined as a set of edges which has at least one edge in common with
any SST on P.

First, we give a complete characterization of the blockers which are
smallest w.r.t. the number of edges. Concretely, we show that these are
either stars (i.e., trees of diameter 2) or special structures called
"caterpillars" , that were first studied by Harary and Schwenk in 1971,
and appear in diverse applications in graph theory.

Then we use the minimal blockers to give an almost complete
characterization of the center of G(P). We show that all the elements of
the center are minimal blockers, and that all the "caterpillar" minimal
blockers are elements of the center. Thus, the only remaining case is the
stars, for which we show that some are elements of the center, while
others are not.

Based on joint works with Micha Perles, Eduardo Rivera-Campo, and
Virginia Urrutia-Galicia.

*************************************************************************
You are all invited! Graduate students are especially welcome.