CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Broadcast and Algorithms
Chair: Hovhannes Harutyunyan (Concordia University)

SIRMA CAGIL ALTAY, Concordia University
Broadcasting on Kn{\"o}del graphs and minimum average broadcast graphs  [PDF]

Broadcasting in a graph, ${G}$, on ${n}$ vertices, consists of spreading a message from one vertex to all other vertices. If broadcasting from any originator can finish in ${\lceil log~n \rceil}$ time units, ${G}$ is called minimal broadcast graph; if the number of edges is the minimum possible, ${B(n)}$, ${G}$ becomes a minimum broadcast graph. In this paper, we will enhance studies about broadcasting on a specific topology called Kn{\"o}del graph, helping us to extend upper bound for ${B(n)}$ and to find minimum average broadcast graphs for a wider range of integers. This is a joint work with Hovhannes Harutyunyan.

PUSPAL BHABAK, Concordia University, Montreal, Canada
Broadcast Problem in k-paths Connected at Two Junctions  [PDF]

Abstract - The broadcast problem is to spread the knowledge of one processor called the originator to all other processors in the network by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. In this paper we will consider the broadcast problem in k-paths connected at two junctions and each path consists of several vertices. We present a $O(|V| + k^{2})$ algorithm to find the broadcast time of multi-path graph with $k$ paths. This is a joint work with Hovhannes Harutyunyan.

PATRICK GASKILL, Virginia Commonwealth University
The Independence Number Project: Difficult Graphs and Conjectures  [PDF] [SLIDES]

The independence number can be computed efficiently for many graph classes, either because they are belong to class of graphs where an efficient algorithm exists (for example, claw-free graphs), or because efficiently computable upper and lower bounds predict the value of this invariant. We discuss a project to extend independence number theory and to find new graph classes where the independence number can be efficiently computed.

In particular we discuss computer-generated conjectures arising from graphs whose independence number cannot be predicted by known efficiently computable upper and lower bounds.

JAN GOEDGEBEUR, Ghent University
House of Graphs: a database of interesting graphs  [PDF] [SLIDES]

In this talk we will present a new searchable database of graphs. Next to complete lists of some graph classes (such as fullerenes or snarks), also a list of graphs that already turned out to be {\em interesting} and {\em relevant} in the study of graph theoretic problems is offered. We will demonstrate how users can perform queries on this database and how they can add new {\em interesting} graphs to it.

House of Graphs is accessible at

Diametral Broadcast Graphs  [PDF]

The paper studies the family of graphs for which the broadcast time equals to its diameter. Such graphs are called $diametral$ $broadcast$ $graphs$ ($dbg$). Broadcasting is the process of message dissemination from an originator vertex of a given graph to all the vertices of the graph. It is known that $D+1 \leq n \leq 2^D$ for a graph on $n$ vertices and of diameter $D$. To cover all possible values of $n$ and $D$ three different graph constructions are presented. It is interesting that every vertex in these graphs receives the message from given originator via a shortest path.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland