Contributions at the Interface Between Algebra and Graph Theory

trigonometric identity;spanning tree;Combinatorics and Optimization

Bibak, Khodakhast

University of Waterloo

关键词: trigonometric identity;    spanning tree;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/7177/1/Bibak_Khodakhast.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries.In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros oflacunary polynomials and a bound on the so-called domination number of a graph.In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry andHuckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a wayto attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero.In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some ofthese identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of thewell-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanningtrees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, wedo not use zeta functions in our arguments.In Chapter 5, we present the conclusion and also some possible projects.