Edge-Regular Graphs with Lambda=2

Abstract

A graph G is edge-regular with parameters n, d, and λ if V(G)=n, the degree of every vertex of G is d, and for any pair of adjacent vertices u and v, N_G(u)∩N_G(v)=λ. We say such graphs are in ER(n,d,λ). In this dissertation we examine properties of edge-regular graphs, especially those with d=6 and λ=2. In particular, multiple infinite families of graphs in ER(n,6,2) are exhibited, and it is shown that ER(n,6,2) contains a connected graph for each n≥12. Several ways of obtaining edge-regular graphs from old ones are discussed. These come in the form of a graph transformation called the triangle graph, in addition to multiple graph products.