Bounded Complete Embedding Graphs, Extended Version

Abstract

This is the extended version of my dissertation, "Bounded Complete Embedding Graphs." This version is presented in three parts, each in a separate file.

[Part 1] Bounded Complete Embedding Graphs [Part 2] Extension A: The Superspectra of the Cohorts of Even Cycles, Revisited [Part 3] Extension B: Satisfactory Divisors for the Dovetail Construction, Revisited

In the dissertation, we define bounded complete embedding graphs and bounded embedding graphs; establish that all bounded embedding graphs are bounded complete embedding graphs, but not conversely; show that all bounded complete embedding graphs are bipartite; and identify several infinite families of bounded complete embedding graphs.

One family of graphs receives particular attention: the cohorts of even cycles. The p-cohort of the 2k-cycle is the graph consisting of p vertex-disjoint copies of the 2k-cycle. In Chapter 4, we prove several results about the nature of the superspectrum of the p-cohort of the 2k-cycle; using these results, we have computed the exact superspectrum of this graph for all pairs of values of p and k such that p and k are both between 2 and 128. A few examples are given in Appendix A, along with the Python code we implemented to complete the necessary computations; the complete list of these superspectra is presented in the tables in Extension A.

Also in Chapter 4, we develop the Dovetail Construction, which allows us to build certain designs that are needed in order to obtain our bounded complete embedding graph results. Each time we apply this construction, we must verify its hypotheses, which include the existence, for certain numbers, of a divisor satisfying certain properties. We employ a short computer program to accomplish the necessary computations for these verifications; the Python code for this program is given in Appendix B, along with a complete listing of verification data for a few selected pairs of values of p and k. We have completed the verification computations for all pairs of values of p and k such that p and k are both between 2 and 128; full details are given for all pairs in the tables in Extension B.