Back to search

University of Waterloo

Bipartite Distance-Regular Graphs of Diameter Four

Abstract

dc:description.abstract

Using a method by Godsil and Roy, bipartite distance-regular graphs of diameter four can be used to construct \{0,α\}-sets, a generalization of the widely applied equiangular sets and mutually unbiased bases. In this thesis, we study the properties of these graphs. There are three main themes of the thesis. The first is the connection between bipartite distance-regular graphs of diameter four and their halved graphs, which are necessarily strongly regular. We derive formulae relating the parameters of a graph of diameter four to those of its halved graphs, and use these formulae to derive a necessary condition for the point graph of a partial geometry to be a halved graph. Using this necessary condition, we prove that several important families of strongly regular graphs cannot be halved graphs. The second theme is the algebraic properties of the graphs. We study Krein parameters as the first part of this theme. We show that bipartite-distance regular graphs of diameter four have one ``special" Krein parameter, denoted by $\krein$. We show that the antipodal bipartite distance-regular graphs of diameter four with $\krein=0$ are precisely the Hadamard graphs. In general, we show that a bipartite distance-regular graph of diameter four satisfies $\krein=0$ if and only if it satisfies the so-called $Q$-polynomial property. In relation to halved graphs, we derive simple formulae for computing the Krein parameters of a halved graph in terms of those of the bipartite graph. As the second part of the algebraic theme, we study Terwilliger algebras. We describe all the irreducible modules of the complex space under the Terwilliger algebra of a bipartite distance-regular graph of diameter four, and prove that no irreducible module can contain two linearly independent eigenvectors of the graph with the same eigenvalue. Finally, we study constructions and bounds of \{0,α\}-sets as the third theme. We present some distance-regular graphs that provide new constructions of \{0,α\}-sets. We prove bounds for the sizes of \{0,α\}-sets of flat vectors, and characterize all the distance-regular graphs that yield \{0,α\}-sets meeting the bounds at equality. We also study bipartite covers of linear Cayley graphs, and present a geometric condition and a coding theoretic condition for such a cover to produce \{0,α\}-sets. Using simple operations on graphs, we show how new \{0,α\}-sets can be constructed from old ones.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Huang, Junbo

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/8618

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Huang, Junbo. Bipartite Distance-Regular Graphs of Diameter Four. University of Waterloo, 2014. http://hdl.handle.net/10012/8618