Cyclic automorphic graph decompositions

Chapter 1 introduces the tools and mechanics necessary for this report. Basic definitions and topics of graph theory which pertain to the report and discussion of automorphic decompositions will be covered in brief detail. An automorphic decomposition D of a graph H by a graph G is a G-decomposition of H such that the intersection of graph (D) @H. H is called the automorhpic host, and G is the automorphic divisor. We seek to find classes of graphs that are automorphic divisors, specifically ones generated cyclically. Chapter 2 discusses the previous work done mainly by Beeler. It also discusses and gives in more detail examples of automorphic decompositions of graphs. Chapter 2 also discusses labelings and their direct relation to cyclic automorphic decompositions. We show basic classes of graphs, such as cycles, that are known to have certain labelings, and show that they also are automorphic divisors. In Chapter 3, we are concerned with 2-regular graphs, in particular rCm, r copies of the m-cycle. We seek to show that rCm has a ρ-labeling, and thus is an automorphic divisor for all r and m. we discuss methods including Skolem type difference sets to create cycle systems and their correlation to automorphic decompositions. In the Appendix, we give classes of graphs known to be graceful and our java code to generate ρ-labelings on rCm.

Fixed block configuration GDDs with block size 6 and (3, r)-regular graphs

Chapter 1 is used to introduce the basic tools and mechanics used within this thesis. Most of the definitions used in the thesis will be defined, and we provide a basic survey of topics in graph theory and design theory pertinent to the topics studied in this thesis. In Chapter 2, we are concerned with the study of fixed block configuration group divisible designs, GDD(n; m; k; λ1; λ2). We study those GDDs in which each block has configuration (s; t), that is, GDDs in which each block has exactly s points from one of the two groups and t points from the other. Chapter 2 begins with an overview of previous results and constructions for small group size and block sizes 3, 4 and 5. Chapter 2 is largely devoted to presenting constructions and results about GDDs with two groups and block size 6. We show the necessary conditions are sufficient for the existence of GDD(n, 2, 6; λ1, λ2) with fixed block configuration (3; 3). For configuration (1; 5), we give minimal or nearminimal index constructions for all group sizes n ≥ 5 except n = 10, 15, 160, or 190. For configuration (2, 4), we provide constructions for several families ofGDD(n, 2, 6; λ1, λ2)s. Chapter 3 addresses characterizing (3, r)-regular graphs. We begin with providing previous results on the well studied class of (2, r)-regular graphs and some results on the structure of large (t; r)-regular graphs. In Chapter 3, we completely characterize all (3, 1)-regular and (3, 2)-regular graphs, as well has sharpen existing bounds on the order of large (3, r)- regular graphs of a certain form for r ≥ 3. Finally, the appendix gives computational data resulting from Sage and C programs used to generate (3, 3)-regular graphs on less than 10 vertices.

WEAK ISOMETRIES OF HAMMING SPACES

In this thesis we study weak isometries of Hamming spaces. These are permutations of a Hamming space that preserve some but not necessarily all distances. We wish to find conditions under which a weak isometry is in fact an isometry. This type of problem was first posed by Beckman and Quarles for Rn. In chapter 2 we give definitions pertinent to our research. The 3rd chapter focuses on some known results in this area with special emphasis on papers by V. Krasin as well as S. De Winter and M. Korb who solved this problem for the Boolean cube, that is, the binary Hamming space. We attempted to generalize some of their methods to the non-boolean case. The 4th chapter has our new results and is split into two major contributions. Our first contribution shows if n=p or p < n2, then every weak isometry of Hnq that preserves distance p is an isometry. Our second contribution gives a possible method to check if a weak isometry is an isometry using linear algebra and graph theory.