Designs and cycle decompositions

图可以被认为是网络的数学表示；它由顶点的集合(通常表示为点)和表示顶点之间关系的边(连接成对的顶点的线)组成。假设在一个图中，我们从顶点v开始，遍历一系列边，每条边都与前一条边相邻。如果我们返回到v而没有沿途重复任何顶点，则我们已经遍历了一个循环，其长度等于遍历的边数。图的圈分解是图的边集到圈的划分。高结构图的圈分解，例如完全图(每对顶点都有一条边连接)和完全多部图(其顶点在不同部分中出现，任意对之间的边在不同部分中)，可以被认为是一类组合设计，并在某些类型的统计实验的设计中有应用。例如，考虑D.H.Rees的一篇论文(Some Design of Use in Sergology，Biometrics，23(1967)，779-791)中描述的以下例子。一位生物学家正在使用一种名为Ouchterlony凝胶扩散技术的方法进行一种涉及多种病毒类型的测试。她可以在培养皿中的抗体周围将k种病毒样本排列成圆形。当病毒和抗体发生反应时会形成沉淀物，相邻样本之间的沉淀物的形状表明抗体是否对两者的共同成分有反应。出于这个原因，她想要设计她的实验，使每一对病毒相邻出现一次；将v个顶点上的完整图分解成长度为k的圈，她就可以做到这一点。如果病毒是在一个家族中出现的，而一个家族的不同成员不能被比较，那么一个完整的多部图的分解是合适的。这个建议将考虑与某些图族的圈分解有关的存在问题，例如完全多部图和完全有向图。此外，还将探索与顶点或圈的着色有关的结构性质的分解，以及与这种分解有关的图的邻接性质。拟议的研究将代表该领域知识的进步，提案中描述的专题与诸如日程安排、编码和通信等领域的应用有关。这项研究将为本科生、研究生和博士后提供培训机会。

A graph can be thought of as a mathematical representation of a network; it consists of a collection of vertices (often represented as points) together with edges (lines joining pairs of vertices) representing relationships between vertices. Suppose that in a graph, we start at a vertex v and traverse a sequence of edges, each adjacent to the previous. If we arrive back at v without repeating any vertex along the way, we have traversed a cycle, whose length equals the number of edges traversed. A cycle decomposition of a graph is a partition of its edge set into cycles. Cycle decompositions of highly structured graphs, such as complete graphs (which have an edge joining each pair of vertices) and complete multipartite graphs (whose vertices occur in parts, with edges between any pair in different parts), can be considered as a class of combinatorial design, and have applications in the design of certain types of statistical experiment.  Consider, for instance, the following example described in a paper of D.H. Rees (Some designs of use in serology, Biometrics 23 (1967), 779-791). A biologist is conducting a test involving v types of virus using a method called the Ouchterlony gel diffusion technique.  She can arrange k virus samples in a circular shape around an antibody in a Petri dish. Precipitates form when a virus and antibody react, and the shape of a precipitate between neighbouring samples indicates whether the antibody is responding to a common component of the two. For this reason, she wants to design her experiment so that each pair of viruses appear next to each other once; a decomposition of the complete graph on v vertices into cycles of length k allows her to do this. If the viruses occur in families, where different members of a family are not to be compared, a decomposition of a complete multipartite graph would be appropriate. This proposal will consider existence questions related to cycle decompositions of certain families of graphs such as complete multipartite graphs and complete directed graphs. Additionally, decompositions with structural properties related to colouring of vertices or cycles will be explored, as will adjacency properties of graphs related to such decompositions. The proposed research will represent an advancement of knowledge in the area and the topics described in the proposal have connections to applications in areas such as scheduling, codes and communications. The research will provide opportunity for training at the undergraduate, graduate and postdoctoral levels.