| The circulant graph Cn,S is the graph on n vertices (with labels 0, 1, 2,..., n - 1), spread around a circle, where two vertices u and v are adjacent iff their (minimum) distance |u- v| appears in set S. In this thesis, we provide a comprehensive analysis of the independence polynomial I (G, x), when G = Cn,S is a circulant. The independence polynomial is the generating function of the number of independent sets of G with k vertices, for k ≥ 0.; While it is NP-hard to determine the independence polynomial I(G, x) of an arbitrary graph G, we are able to determine explicit formulas for I( G, x) for several families of circulants, using techniques from combinatorial enumeration. We then describe a recursive construction for an infinite family of circulants, and determine the independence number of each graph in this family. We use these results to provide four applications, encompassing diverse areas of discrete mathematics. First, we determine a new (infinite) family of star extremal graphs. Secondly, we obtain a formula for the chromatic number of infinitely many integer distance graphs. Thirdly, we prove an explicit formula for the generalized fractional Ramsey function. Finally, we determine the optimal Nordhaus-Gaddum inequalities for the fractional chromatic and circular chromatic numbers. These new theorems significantly extend what is currently known.; Building on these results, we develop additional properties and applications of circulant graphs. We determine a full characterization of all graphs G for which its line graph L(G) is a circulant; and apply our previous theorems to calculate the list colouring number of a specific family of circulants. We then characterize well-covered circulant graphs, and examine the shellability of their independence complexes. We conclude the thesis with a detailed analysis of the roots of I (Cn,S, x). Among many other results, we solve several open problems by calculating the density of the roots of these independence polynomials; leading to new theorems on the roots of matching polynomials and rook polynomials. |
