CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Average Graph Parameters - Part I
Org: Lucas Mol et Ortrud Oellermann (University of Winnipeg)

PENGYU LIU, Simon Fraser University
A polynomial metric on rooted binary tree shapes  [PDF]

In this talk, we will define a polynomial and show that the polynomial characterizes all rooted binary tree shapes, that is, two unlabeled rooted binary trees are isomorphic if and only if their corresponding polynomials are identical. Metrics on rooted binary tree shapes can be defined using this characterizing polynomial. We will show that these metrics can distinguish random tree shapes generated by different models as well as phylogenetic trees of seasonal and tropical influenza. Finally, we will introduce some mathematical conjectures about and generalizations of the polynomial and its future applications in computational biology and other sciences.

LUCAS MOL, University of Winnipeg
The Mean Subtree Order and the Mean Connected Induced Subgraph Order  [PDF]

The mean connected induced subgraph order of a graph $G$ is the average number of vertices in a connected induced subgraph of $G$. This parameter is an extension of the mean subtree order of a tree. We present a conceptually simple proof of the fact that the path has minimum mean subtree order among all trees of a given order. We then extend these ideas to show that the path has minimum mean connected induced subgraph order among all block graphs of a given order. This is joint work with Kristaps Balodis, Matthew Kroeker, and Ortrud Oellermann.

STEPHAN WAGNER, Stellenbosch University
Extremal subtree densities of trees  [PDF]

The average subtree order $\mu_T$ and the density $D_T = \frac{\mu_T}{n}$ of a tree $T$ with $n$ vertices were first studied in 1983 by Jamison. While the minimum density is attained by a path, the structure of the trees that attain the maximum is more complicated. It is conjectured that the trees of maximum density must be caterpillars. We lend some support to this conjecture by proving that the extremal tree must have large diameter (close to $n$). We also show that the maximum density is asymptotically equal to $1 - \frac{2\log_2 n}{n} + O (\frac{\log \log n}{n})$.

HUA WANG, Georgia Southern University
Average distance between leaves and peripheral vertices  [PDF]

Given a tree $T$ and the set of leaves $L(T)$, the Gamma index (also known as the terminal Wiener index) $\Gamma(T)$ is the sum of distances between all pairs of leaves. We will investigate the average distance between leaves in a tree $T$, called {\it the normalized Gamma index} and denoted by $\hat{\Gamma}(T)$. Some extremal trees under various constraints that maximize or minimize $\hat{\Gamma}(T)$ are identified or partially characterized. Many questions remain.

The average distance between peripheral vertices will also be discussed. This is joint work with Heather Smith.