Finding Edge and Vertex Induced Cycles within Circulants.

<p>Let <em>H</em> be a graph. <em>G</em> is a subgraph of <em>H</em> if <em>V</em> (<em>G</em>) &#8838; <em>V</em> (<em>H</em>) and <em>E</em>(<em>G</em>) &#8838; <em>E</em>(<em>H</em>). The subgraphs of <em>H</em> can be used to determine whether <em>H</em> is planar, a line graph, and to give information about the chromatic number. In a recent work by Beeler and Jamison [3], it was shown that it is difficult to obtain an automorphic decomposition of a triangle-free graph. As many of their examples involve circulant graphs, it is of particular interest to find triangle-free subgraphs within circulants. As a cycle with at least four vertices is a canonical example of a triangle-free subgraph, we concentrate our efforts on these. In this thesis, we will state necessary and sufficient conditions for the existence of edge induced and vertex induced cycles within circulants.</p>

Name thesis:degree_name

MS (Master of Science)

Level thesis:degree_level

Thesis - unrestricted

Discipline thesis:degree_discipline

Mathematical Sciences

Year dc:date.issued

2008

Author dc:creator

• Wooten, Trina Marcella

• graph theory
• circulants
• subgraphs
• cycles
• Discrete Mathematics and Combinatorics
• Mathematics
• Physical Sciences and Mathematics

Statement dc:rights

• Copyright by the authors.

Repository record dc:identifier

https://dc.etsu.edu/etd/1985

OAI identifier oai:identifier

oai:dc.etsu.edu:etd-3337