Designs and cycle decompositions

点击翻译按钮获取中文摘要

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. **