A Gluing Scheme for Maximal-Girth Tree-Decomposed Graphs

Daniel Pinto
University of Coimbra

Ethan Cotterill
Universidade Federal Fluminense

PDF

Minisymposium: COMBINATORICS

Content: If we take three perfect binary trees of the same height we can build a trivalent graph, that we will call \emph{quasi-binary tree}, by adding an edge from each one of the three root vertices of the original trees to a new vertex. We will show that, for all $n \in \mathbb{N}$, there is a way of gluing three quasi-binary trees of the same height $n$ such that the girth of the connected graph, that results from identification of the leaves, has the maximal possible value, that is: $2n+2$.

Back to all abstracts