#### Date of Award

12-2014

#### Degree Type

Masters Thesis

#### Degree Name

Master of Science (MS)

#### Department

Mathematics

#### Committee Chair

Jeremy Lyle

#### Committee Chair Department

Mathematics

#### Committee Member 2

James Lambers

#### Committee Member 2 Department

Mathematics

#### Committee Member 3

John Harris

#### Committee Member 3 Department

Mathematics

#### Abstract

In the following thesis, the structure and properties of *G *and its clique graph *cl*_{t}* *(*G*) are analyzed for graphs *G *that are non-complete, regular with degree *δ *, and where every edge of *G *is contained in a *t *-clique. In a clique graph *cl*_{t}* *(*G*), all cliques of order *t *of the original graph *G *become the clique graph’s vertices, and the vertices of the clique graph are adjacent if and only if the corresponding cliques in the original graph have at least 1 vertex in common. This thesis mainly investigates if properties of regular graphs are carried over to clique graphs of regular graphs. In particular, the first question considered is whether the clique graph of a regular graph must also be regular. It is shown that while line graphs, *cl*_{2}(*G*), of regular graphs are regular, the degree difference of the clique graph *cl*_{3}(*R*) can be arbitrarily large using *δ *-regular graphs *R *with *δ **≥ *3. Next, the question of whether a clique graph can have a large independent set is considered (independent sets in regular graphs can be composed of half the vertices in the graph at the most). In particular, the relation between the degree difference and the independence number of *cl*_{t}* *(*G*) will be analyzed. Lastly, we close with some further questions regarding clique graphs.

#### Recommended Citation

Burmeister, Jan, "The Structure and Properties of Clique Graphs of Regular Graphs" (2014). *Master's Theses*. 77.

http://aquila.usm.edu/masters_theses/77