Average Graph Parameters - Part II
Org: Lucas Mol et Ortrud Oellermann (University of Winnipeg)
[PDF]

Asymptotic resolution of a question of Plesník  [PDF]

Fix $d \ge 3$. We show the existence of a constant $c>0$ such that any graph of diameter at most $d$ has average distance at most $d-c \frac{d^{3/2}}{\sqrt n}$, where $n$ is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of $c$. This constitutes an asymptotic solution to a longstanding open problem of Plesník. Furthermore we solve that open problem of Plesník exactly for digraphs in case the order is large compared with the diameter.

PETER DANKELMANN, University of Johannesburg
The average distance of maximal planar graphs  [PDF]

The average distance $\mu(G)$ of a finite connected graph $G$ is defined as the arithmetic mean of the distances between all pairs of distinct vertices of $G$. We show that for every maximal planar graph $G$ of order $n$, $\mu(G) \leq \frac{1}{18}n +O(n^{1/2}),$ which asymptotically proves a recent conjecture by Che and Collins. We further show that this bound can be improved for $4$-connected and $5$-connected maximal planar graphs. \This is joint work with Eva Czabarka, Trevor Olsen, and Laszlo Szekely.

SUIL O, State University of New York, Korea
Average connectivity and average edge-connectivity in graphs  [PDF]

Connectivity and edge-connectivity of a graph measure the difficulty of breaking the graph apart, but they are very much affected by local aspects like vertex degree. Average connectivity (and analogously, average edge-connectivity) has been introduced to give a more refined measure of the global “amount” of connectivity. In this talk, we prove a relationship between the average connectivity and the matching number in graphs. We also give the best lower bound for the average edge-connectivity over $n$-vertex connected cubic graphs. In addition, we show that this family has the fewest perfect matchings among cubic graphs that have perfect matchings.

ORTRUD OELLERMANN, University of Winnipeg
The average connectivity of minimally $2$-connected graphs  [PDF]

The connectivity between a pair $u,v$ of vertices in a graph equals the maximum number of pairwise internally disjoint $u$--$v$ paths. The average connectivity, $\overline{\kappa}(G)$ of a graph $G$, is the average connectivity between pairs of vertices taken over all pairs. Minimally $2$-connected graphs with maximum average connectivity are characterized. It is shown that $\overline{\kappa}(G)\le 9/4$ if $G$ is minimally $2$-connected. For a graph $G$, $\overline{\kappa}_{\max}(G)$ is the maximum average connectivity among all orientations of $G$. We obtain upper and lower bounds for $\overline{\kappa}_{\max}(G)$ and for $\overline{\kappa}_{\max}(G)/\overline{\kappa}(G)$ for all minimally $2$-connected graphs $G$. Sharpness for the various bounds is discussed.