Doctoral Thesis Defense: Zhiyuan Li
Speaker: Zhiyuan Li
Supervisor: Dr. H. Harutyunyan
Examining Committee: Drs. T. Fevens, L. Narayanan, R. Soleymani, J. Y. Yu (Chair)
Title: Improved Upper Bounds and Lower Bounds on Broadcast Function
Date: Monday, December 11, 2017
Time: 10:30 a.m.
Place: EV 11.119
Given a graph G = (V,E) and an originator vertex v, broadcasting is an information disseminating process of transmitting a message from vertex v to all vertices of graph G as quickly as possible. A graph G on n vertices is called broadcast graph if the broadcasting from any vertex in the graph can be accomplished in time. A broadcast graph with the minimum number of edges is called minimum broadcast graph. The number of edges in a minimum broadcast graph on n vertices is denoted by B(n). A long sequence of papers present different techniques to construct broadcast graphs and to obtain upper bounds on B(n). In this thesis, we study the compounding and the vertex addition broadcast graph constructions, which improve the upper bound on B(n). We also present the first nontrivial general lower bound on B(n).