Date of Award
8-2007
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Jamison, Robert E
Abstract
Let G and H be graphs. A G-decomposition D of a graph H is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. It is well known that a graceful labelling (or more generally a rho-valuation) of a graph G induces a cyclic G-decomposition of a complete graph. We will extend these notions to that of a general valuation in a cyclic group. Such valuations yield decompositions of circulant graphs. We will show that every graph has a valuation and hence is a divisor of arbitrarily large circulant graphs.
Let D be a G-decomposition of H. The intersection graph generated by the decomposition D, denoted I(D), has a vertex for each part of the partition and an edge if the parts of the partition share a common node in H. While the problem of determining whether a G-decomposition of H exists is a well-studied one, the structure of the resulting intersection graph has not been the subject of much research. As such, we are interested in the structure of these graphs. Of specific interest is whether there exist H, G, and a G-decomposition of H such that the resulting intersection graph is isomorphic to H. A decomposition D such that I(D)=H is said to be automorphic (``self-shaped''). If a graph H is able to host an automorphic decomposition, then we say that H is an automorphic host. Similarly, if there exists an H such that there exists an automorphic G-decomposition of H, then we say that G is an automorphic divisor.
In this dissertation, we will give several necessary conditions for the existence of an automorphic G-decomposition of H. These will allow us to examine the problem of which graphs are automorphic hosts. We conjecture that only even regular graphs are able to host an automorphic decomposition.
This dissertation will also examine the problem of which graphs are automorphic divisors. We conjecture that every graph is an automorphic divisor.
Recommended Citation
Beeler, Robert, "Automorphic Decompositions of Graphs" (2007). All Dissertations. 92.
https://open.clemson.edu/all_dissertations/92