Average Graph Parameters II
[PDF]

ANTE CUSTIC, Simon Fraser University
Algorithms for $2$-median problems on trees with small number of leaves  [PDF]

Given a tree with weights assigned to vertices and lengths to edges, the $p$-median problem on trees is a problem of finding $p$ locations in the tree, so that the sum of weighted distances to the closest location for all vertices is minimized. Optimal solution for $p=1$ is the weighted centroid of a tree, which can be found in $O(n)$ time, while best known bound for $p=2$ is $O(n\log n)$ which is given by Gavish and Sridhar in 1995. In this talk we improve this result when the number of leaves is small, i.e. we present $O(n\log s)$ time algorithm for the $2$-median problem on trees, where $s$ denotes the number of leaves. Furthermore, we give $O(n\log s)$ algorithms for the generalizations of the $2$-median problems on trees, when two medians need to satisfy distance and eccentricity constrains, respectively. This is a joint work with Rashmisnata Acharyya and Binay Bhattacharya.

DONOVAN HARE, Dept. of Math., University of British Columbia, Kelowna, BC
Tools for Constructing and Counting Odd Cycles in Graphs  [PDF]

A graph is $k$-critical if it can be colored in no fewer than $k$ colors and its proper subgraphs can be color in fewer than $k$ colors. The 3-critical graphs are just the odd cycles but for $k\geq 4$ the structure of $k$-critical graphs has no known nice characterization.

In 1984, T.~Gallai asked whether a $k$-critical graph on $n$ vertices contains $n$ distinct $(k-1)$-critical subgraphs (this is Problem 5.9 of T.~Jensen \& B.~Toft's book Graph Coloring Problems''). This talk gives an affirmative answer to Gallai's question restricted to 4-critical graphs by proving they contain at least $\frac{8}{3}n-\frac{29}{3}$ odd cycles. Abbott and Zhou (1993) proved the previous best lower bound: $\sqrt[3]{6n}$.

FADEKEMI JANET OSAYE, University of Johannesburg, South Africa
Average eccentricity, k-packings and k-dominations in graphs  [PDF]

Let $G$ be a connected graph of order $n$. The eccentricity $e_G(v)$ of a vertex,$v$ in $G$ is the distance from $v$ to a vertex farthest from $v$ in $G$. The average eccentricity $avec(G)$ of $G$ is defined as $avec(G)= \frac{1}{n}\sum_{v\in V(G)} e_G(v)$. Given $k\in \mathbb{N}$, a $k$-packing of $G$ is a subset $S\subseteq V(G)$ such that the distance between any two vertices in $S$ is at least $k+1$. The maximum cardinality of a $k$-packing of $G$ is the $k$-packing number $\beta_k(G)$ of $G$. A subset $D\subseteq G$ is a $k$-dominating set of $G$ if each vertex of $G$ is within distance at most $k$ from some vertex in $D$. The minimum cardinality of a $k$-dominating set of $G$ is the $k$-domination number $\gamma_k(G)$ of $G$. In this talk we present old and new bounds on the average eccentricity of $G$ of given order and $k$-packing number or $k$-domination number.

FEIRAN YANG, University of Victoria
$k$-Broadcast domination and $k$-multipacking  [PDF]

Imagine transmitters located at the vertices of a graph $G$. The transmitter at each vertex $v$ broadcasts a signal of integer \emph{strength} $f(v) \geq 0$; a broadcast of positive strength from $v$ is \emph{heard} by all vertices at distance at most $f(v)$ from $v$. If every vertex hears broadcasts from at least $k$ different vertices, then the function $f$ is called a \emph{$k$-dominating broadcast}. The \emph{cost} of a $k$-dominating broadcast is $\sum\limits_{v \in V} f(v)$. The \emph{$k$-broadcast domination number} of $G$, $\gamma_{b_k}(G)$, is the smallest cost of a $k$-dominating broadcast. The 1-broadcast domination number is known as the broadcast domination number, and has been well-studied.

In this talk we will outline the basic theory of $k$-broadcast domination and the dual problem, \emph{$k$-multipacking}, and give a bound on $\gamma_{b_2}(G)$ in terms of the number of vertices of $G$.