The Structure and Properties of Clique Graphs of Regular Graphs

<p>In the following thesis, the structure and properties of <em>G </em>and its clique graph <em>cl</em>_<em>t</em><em> </em>(<em>G</em>) are analyzed for graphs <em>G </em>that are non-complete, regular with degree <em>δ </em>, and where every edge of <em>G </em>is contained in a <em>t </em>-clique. In a clique graph <em>cl</em>_<em>t</em><em> </em>(<em>G</em>), all cliques of order <em>t </em>of the original graph <em>G </em>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, <em>cl</em>₂(<em>G</em>), of regular graphs are regular, the degree difference of the clique graph <em>cl</em>₃(<em>R</em>) can be arbitrarily large using <em>δ </em>-regular graphs <em>R </em>with <em>δ </em><em>≥ </em>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 <em>cl</em>_<em>t</em><em> </em>(<em>G</em>) will be analyzed. Lastly, we close with some further questions regarding clique graphs.</p>

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Masters Thesis

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2014

Author dc:creator

• Burmeister, Jan

Contributors dc:contributor

• Jeremy Lyle
• James Lambers
• John Harris

• clique graph
• regular graph
• line graph
• degree difference
• independence number
• Other Mathematics
• Physical Sciences and Mathematics

Repository record dc:identifier

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

OAI identifier oai:identifier

oai:aquila.usm.edu:masters_theses-1057