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,

Stephen Locke
(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