CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013

Chair: Hovhannes Harutyunyan (Concordia University)
[PDF]

SIRMA CAGIL ALTAY, Concordia University

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.

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 http://hog.grinvin.org

HOVHANNES HARUTYUNYAN, Concordia University
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.