FAU > Science > Mathematics > Symposion > Abstract
Fall 2013/ Spring 2014
Symposion on Enumerative Combinatorics
On Friday, April 4, at 2:55 p.m. in SE 215,
(Florida Atlantic Univerisity)
will give a Colloquium talk about
Non-Separating Trees and Cohesion
Abstract: There is an old and easy exercise that requires students to show that a connected graph has a vertex v such that G-v is connected. Lovasz asked students to prove that if G is a connected graph with no two vertices of degree one at distance two, then G has a 2-vertex path P such that G-V(P) is connected. This speaker looked for a generalization of this problem.
A non-trivial connected graph G is m-cohesive if for every pair of distinct vertices u,v, the sum d(u)+d(v)+d(u,v) is at least m. Here, d(v) is the degree of vertex v and d(u,v) is the distance from u to v. The conjecture is that if G is (2k)-cohesive, k > 2, and if T is a tree on k vertices, then G has a non-separating copy of T. In the special case in which T is a path, this was proven by Locke, Voss and Tracy. (Note, Lovasz's result has k=2, but 4-cohesive is not sufficient.)
Modifying the statement of the conjecture, we could ask for f(T) to be the minimum value of m such that every m-cohesive graph has a non-separating copy of T. We show that f(T) is at most 2k+2 for any tree on k vertices. For the case k=4, we conducted a small computer search for 7-cohesive 2-connected graphs which fail to have a non-separating claw.
Some of the results mentioned are joint work with my current Ph.D. student, Chenchu Gottipati
All are welcome!
Last modified: by Markus Schmidmeier