CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Average Graph Parameters I
Org: Ortrud Oellermann and Lucas Mol (University of Winnipeg)

DANIELLE COX, Mount Saint Vincent University
The Average Reliability of a Graph  [PDF]

Let $G$ be a finite simple graph. The all-terminal reliability of a $G$, Rel$(G,p)$ is the probability that at least a spanning tree is operational, given that vertices always operate and edge independently operate with probability $p\in [0,1]$. It is known that most optimal graphs do not always exist. We will discuss a new measure of optimality, the average reliability of a graph $G$, avgRel$(G)$. This talk will examine the properties of this parameter and use it to propose near optimal graphs. This is joint work with Jason Brown (Dalhousie University) and Richard Ehrenborg (University of Kentucky).

PETER DANKELMANN, University of Johannesburg
Bounds on the average distance of directed graphs  [PDF]

The average distance of a strong digraph $D$ of order $n$ is defined as \[ \mu(D) = \frac{1}{n(n-1)} \sum_{u,v \in V(D)} d(u,v), \] where $d(u,v)$ is the distance from $u$ to $v$.

We give an asymptotically sharp upper bound on $\mu$ for tournaments of given order and edge-connectivity, strengthening a bound by Plesnik for tournaments of given order.

For strong digraphs of given order and minimum out-degree $\delta$ there is no upper bound on $\mu$ of the form $c_{\delta} n+O(1)$ with $c_{\delta} \rightarrow 0$ as $\delta \rightarrow \infty$. We show that such a bound exists for Eulerian digraphs.

LUCAS MOL, University of Winnipeg
Maximizing mean subtree order for classes of trees  [PDF]

We consider the average order of a subtree of a tree. While it is known that the path of order $n$ minimizes this mean among all trees of order $n$, the structure of the trees that maximize the mean is unknown. Jamison conjectured that any such tree is a caterpillar. We consider this problem for certain classes of trees, including trees with a fixed diameter and trees with a fixed number of leaves. Finally, we consider an extension of this mean to general connected graphs, where we concentrate on the unicyclic case.

ORTRUD OELLERMANN, University of Winnipeg
On the mean order of sub-$k$-trees of $k$-trees  [PDF]

In this talk we show that the problem of finding the mean order of all sub-$k$-trees, containing a fixed $k$-clique, can be reduced to that of finding the mean order of subtrees of a tree containing a fixed vertex. We describe two extensions of this problem and present sharp lower bounds in both cases. The talk concludes with an introduction of global mean orders of sub-$k$-trees of a $k$-tree. For the class of simple-clique $k$-trees, we show that the mean order of their sub-$k$-trees is asymptotically equal to the mean subtree order of their duals. (Joint work with Alexander Stephens.)

HUA WANG, Georgia Southern University
On the average subtree order of trees and related studies  [PDF]

We consider the average subtree order of trees, motivated by a question posted by R. Jamison in 1983. The question asks if it is true that a tree with internal vertex degree at least 3 has its average subtree order being at least half of the total number of vertices. We provide a positive answer to this question and generalize it. We also include some recent development on the characteristics of trees of extremal densities. This is based on joint work with Andrew Vince and Stephan Wagner.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology