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.
","abstract_html":"<p>In the following thesis, the structure and properties of <em>G </em>and its clique graph <em>cl</em><sub><em>t</em></sub><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><sub><em>t</em></sub><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><sub>2</sub>(<em>G</em>), of regular graphs are regular, the degree difference of the clique graph <em>cl</em><sub>3</sub>(<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><sub><em>t</em></sub><em> </em>(<em>G</em>) will be analyzed. Lastly, we close with some further questions regarding clique graphs.</p>","abstract_has_math":false,"creators":["Burmeister, Jan"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Masters Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Jeremy Lyle","James Lambers","John Harris"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-01T08:00:00Z","date_published":"2014-12-01T08:00:00Z","updated_at":"2026-07-24T05:44:27Z","subjects":["clique graph","regular graph","line graph","degree difference","independence number","Other Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://aquila.usm.edu/masters_theses/77","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jeremy Lyle","James Lambers","John Harris"]},{"key":"dc:creator","label":"Author","values":["Burmeister, Jan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2014-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["clique graph","regular graph","line graph","degree difference","independence number","Other Mathematics","Physical Sciences and Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://aquila.usm.edu/masters_theses/77"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["The Structure and Properties of Clique Graphs of Regular Graphs"]}]}],"canonical_facts":{"dc:contributor":["Jeremy Lyle","James Lambers","John Harris"],"dc:creator":["Burmeister, Jan"],"dc:date.available":["2014-01-01T08:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://aquila.usm.edu/masters_theses/77"],"dc:subject":["clique graph","regular graph","line graph","degree difference","independence number","Other Mathematics","Physical Sciences and Mathematics"],"dc:title":["The Structure and Properties of Clique Graphs of Regular Graphs"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T05:44:27Z"}