Seminar in Discrete Mathematics – Dense graphs and a conjecture for tree-depth

Speaker: Michael Barrus, URI

Title: Dense graphs and a conjecture for tree-depth

Time: Friday October 14, 1pm, Lippitt 204

Abstract: The tree-depth of a graph $G$ is the smallest number of ordered labels necessary to label the vertices of $G$ so that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is 1-unique if for each vertex $v$ in $G$, there is an optimal tree-depth-labeling of $G$ in which $v$ is the unique vertex receiving the lowest label. In a recent work the author and J. Sinkovic conjectured that all minor-minimal graphs having a fixed tree-depth are necessarily 1-unique. In this talk we study graphs with high tree-depths in relation to their orders. Using these results, a computer search, and a few interesting families of dense graphs, we resolve the 1-uniqueness conjecture and clarify relationships between 1-uniqueness and minor-minimality for tree-depth.