PhD Oral Exam - Mohammadhossein Fakharan, Computer Science

When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.

Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.

Abstract

In a graph G=(V,E), where V and E are the sets of vertices and edges of G, respectively, broadcasting is an information dissemination process of distributing a message from one vertex, which is called the originator, to all other vertices of the graph. Spreading information is one of the important tasks of a modern interconnection network. This process is called broadcasting. A huge amount of research was conducted in this area.

In this thesis, we will mainly focus on structural and algorithmic aspects of broadcasting in special families of graphs, particularly hypercubes and Knödel graphs.

We investigate hypercubes as canonical examples of minimum broadcast graphs, where we develop an algorithm to generate and enumerate all minimum-time broadcast schemes. Our analysis confirms that every such scheme on a hypercube is also a minimum-distance broadcast scheme.

Subsequently, we shift our attention to Knödel graphs, exploring their potential as broadcast graphs under both standard and reversed dimensional broadcast schemes with cyclic shifts and arbitrarily dimension repetitions. We determine all values of n for which these schemes are valid and identify structural properties that maximize broadcast efficiency.

A new general upper bound on the broadcast function B(n) for odd n (excluding n = 2^k - 1) is then established using a vertex deletion approach. In this context, we also resolve an open question concerning the existence of minimum average time broadcast graphs.

Finally, we extend our investigations to generalized Knödel graphs, characterizing the values of n for which they admit certain valid dimensional broadcast schemes. Our results contribute new insights toward understanding the relationship between graph structure and information dissemination efficiency.