CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Average Graph Parameters II

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$.


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