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 vertexvsuch thatG-vis connected. Lovasz asked students to prove that ifGis a connected graph with no two vertices of degree one at distance two, thenGhas a 2-vertex pathPsuch thatG-V(P) is connected. This speaker looked for a generalization of this problem.

A non-trivial connected graphGism-cohesive if for every pair of distinct verticesu,v, the sum d(u)+d(v)+d(u,v) is at leastm. Here, d(v) is the degree of vertexvand d(u,v) is the distance fromutov. The conjecture is that ifGis (2k)-cohesive,k> 2, and ifTis a tree onkvertices, thenGhas a non-separating copy ofT. In the special case in whichTis a path, this was proven by Locke, Voss and Tracy. (Note, Lovasz's result hask=2, but 4-cohesive is not sufficient.)

Modifying the statement of the conjecture, we could ask forf(T) to be the minimum value ofmsuch that everym-cohesive graph has a non-separating copy ofT. We show thatf(T) is at most 2k+2 for any tree onkvertices. For the casek=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