CanaDAM 2021
En ligne, 25 - 28 mai 2021

Average Graph Parameters - Part I
Org: Stijn Cambie (Radboud University Nijmegen, the Netherlands)

EVA CZABARKA, University of South Carolina
Minimum Wiener index of planar triangulations and quadrangulations  [PDF]

The Wiener index of a graph is the sum of distances between all unordered pairs of vertices (or $\binom{n}{2}$ times the average distance, where $n$ is the order of the graph). We will determine the minimum Wiener index of $n$-vertex of $c$-connected planar triangulations and quadrangulations for all possible values of $c$, and find the structure of the extremal graphs for $5$-connected triangulations and $3$ connected quadrangulations.

PETER DANKELMANN, University of Johannesburg
On the Wiener Index of Graphs with Large Maximum Degree  [PDF]

The Wiener index $W(G)$ of a connected graph $G$ is defined as the sum of the distances between all unordered pairs of vertices of $G$.

Best possible upper bounds on the Wiener index in terms of order and either minimum degree or maximum degree were given by Kouider and Winkler, and Plesnik, respectively. In this talk we combine these bounds. Among others, we prove the best possible bound \[ W(G) \leq \binom{n-\Delta+\delta}{2} \frac{n+2\Delta}{\delta+1} + O(n^2), \] for graphs of order $n$, minimum degree $\delta$ and maximum degree $\Delta$.

Joint work with Alex Alochukwu.

LUCAS MOL, The University of Winnipeg
The mean subtree order of graphs under edge addition  [PDF]

A subtree of a graph $G$ is a subgraph of $G$ that is a tree. The mean subtree order of $G$ is the average order of the subtrees of $G$. We conjecture that every non-complete graph $G$ contains a pair of nonadjacent vertices $u$ and $v$ such that adding the edge between $u$ and $v$ increases the mean subtree order, and we prove this conjecture in the case that $G$ is a tree. We discuss several related open problems and conjectures. This is joint work with Ben Cameron (University of Guelph).

The average eccentricity of a graph with prescribed girth  [PDF]

Let $G$ be a connected graph of order $n$. The eccentricity $e(v)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$. The average eccentricity of $G$ is the mean of all eccentricities in $G$. We give upper bounds on the average eccentricity of $G$ in terms of $n$, minimum degree $\delta$, and girth $g$. In addition, we proved that if for given $g$ and $\delta$, there exists a Moore graph, then the bounds are asymptotically sharp. Moreover, we showed that the bounds can be further improved if $G$ has a large degree.

RISTE SKREKOVSKI, University of Ljubljana
Some problems and results on some graph parameters  [PDF]

In the talk I will survey some open problems and results on Wiener index and several other related graph parameters.