Mathematical Sciences: Embeddings and Decompositions of Graphs

数学科学：图的嵌入和分解

• 批准号: 9531722
• 负责人: Christopher Rodger
• 金额: $ 4万
• 依托单位: Auburn University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-09-01 至 2000-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9531722&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Embeddings; Decompositions; 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.

罗杰9531722该奖项是为了表彰对未来三年将考虑的几个问题的研究。其中两个问题需要付出很大努力才能解决。第一个问题是找到n点完全图(Kn)的给定边色副本嵌入到Kv的边色副本中的充要条件，使得由每条颜色的边导出的子图形成Kv的连通生成的k-正则子图。这将是现有结果的一个补充，要么放弃子图是连通的要求，要么用它们是2边连通的要求取而代之。第二个问题是证明了任一n阶指标为L的部分门德尔松三元系都可以嵌入到一个v阶和指标为2n+1的完备的门德尔松三元系中。这是Lindner猜想的定向版本，该猜想现已被用归并技术证明。在无向情况下的这一进展表明，有向类比已准备好被解决。合并技术本身是有意义的，值得进一步研究。其他问题将被研究。研究人员将考虑由汉明码C自然产生的图H(C)，并试图证明H(C)有哈密尔顿分解并且是泛循环的。这位研究人员还计划为日益增长的图形设计文献做出贡献。这项研究属于组合学的一般领域。组合学的目标之一是找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。