Enlarging properties of graphs

Abstract

The subjects of this thesis are the enlarging and magnifying properties of graphs. Upper bounds for the isoperimetric number i(G) of a graph G are determined with respect to such elementary graph properties as order, valency, and the number of three and four-cycles. The relationship between i(G) and the genus of G is studied in detail, and a class of graphs called finite element graphs is shown never to supply enlarging families. The magnifying properties of Hamiltonian cubic graphs are investigated, and a class of graphs known as shift graphs is defined. These are shown never to form enlarging families, using a technical lemma derived from Klawe's Theorem on non-expanding families of graphs. The same lemma is used, in conjunction with some elementary character theory, to prove that several important classes of Cayley graphs do not form enlarging families, and to derive a lower bound on the subdominant eigenvalue of a vertex-transitive graph. The problem of finding Ramanujan graphs is discussed. Some necessary conditions for a graph to be Ramanujan, depending on the automorphism group of the graph, and the number of certain reduced walks in the graph, are derived. Finally, the techniques of Buck are used to construct an infinite number of families of linear expanders, deploying free subgroups of the group SL(2, Z).