Mathematical Sciences: Embeddings and Decompositions of Graphs

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

Rodger 9531722 This award is for a study of several problems that will be considered over the next three years. Two of the problems will take a major effort to solve. The first problem is to find necessary and sufficient conditions for a given edge-colored copy of the complete graph on n vertices (Kn) to be embedded in an edge-colored copy of Kv in such a way that the subgraph induced by the edges of each color form a connected spanning k-regular subgraph of Kv. This would be a companion to existing results with either drop the requirement that the subgraphs are connected or replace it with the requirement that they be 2-edge connected. The second problem is to show that any partial Mendelsohn triple system of order n and index l can be embedded in a complete Mendelsohn triple system of order v and index l for some v not exceeding 2n+1. This is a directed version of Lindner's conjecture, a conjecture which has now been proved for triple systems of even index using amalgamation techniques. This progress in the undirected case suggests that the directed analogue is ready to be solved. Amalgamation techniques are of interest in their own right, and warrant further study. Other problems will be studied. The investigator will consider the graph H(C) naturally arising from a Hamming code C and attempt to show that H(C) has a hamilton decomposition and is pan-cyclic. The investigator also plans to make contributions to the growing literature on graph designs. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.