Date of Award
Fall 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 clt (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 clt (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, cl2(G), of regular graphs are regular, the degree difference of the clique graph cl3(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 clt (G) will be analyzed. Lastly, we close with some further questions regarding clique graphs.
Copyright
2014, Jan Burmeister
Recommended Citation
Burmeister, Jan, "The Structure and Properties of Clique Graphs of Regular Graphs" (2014). Master's Theses. 77.
https://aquila.usm.edu/masters_theses/77