Heffter阵列的构造和图的二嵌入

发布时间：2018-04-25 05:42

  本文选题：幻阵 + Heffter阵列　； 参考：《北京交通大学》2017年硕士论文

【摘要】：用组合设计方法研究完全图在曲面上嵌入是组合设计和图论的重要研究课题.在定向曲面上完全图K2mn+1的二嵌入是一个面2-染色的拓扑嵌入,并使得第一个颜色类构成一个s-圈,另一个颜色类构成一个t-圈[2].Grannel等人[11-13]研究了当s = t= 3时即Steiner三元系(STS)的二嵌入.2010年,Brown[7]构造了一类二嵌入,这类二嵌入使得s,t 一个等于3,另一个等于4.Archdeacon[2]在2014年提出的Heffter阵列的概念推广了 Steiner三元系的二嵌入.Heffter阵列由两个正交的Heffter系构成,从组合设计角度看,一个Heffter系可以构造一个循环的k-圈系.Heffter阵列与完全二部图Km,n流量分配相关,满足一定条件的流量图可以用来构造完全图可定向嵌入.所以,Heffter阵列可以用来构造在可定向曲面上完全图的二嵌入.同年,Archdeacon与Dinitz等人[5]定义了带空位置的整型Heffter方阵H(n;k).他证明H(n;k)存在的必要条件是nk≡ 0,3(mod 4)并猜想这个条件是充分的,并且构造了当k为偶数和nk≡3(mod4)时的H(n;k),对nk≡1(mod 4)给出了部分参数的构造.2015年,Dinitz和Mattern[2]构造了两类不带空的Heffter阵列,即H(3,n)和H(5,n).进一步地,Boothby[6]在他的博士毕业论文中证明了不带空的Heffter阵列存在当且仅当m2,n2.本文主要介绍Heffter阵列和图的二嵌入关系,并构造了一些带空位置的整型Heffter方阵,一共分为四章.第一章,首先介绍有关的基本概念和符号.第二章,介绍了 Heffter阵列和图的二嵌入的关系.第三章,在Archdeancon构造的带空位置的整型Heffter方阵的基础上,构造了某些参数的带空位置的整型Heffter方阵.第四章,对所做的工作进行总结.
[Abstract]:Using the combined design method to study the complete graph embedding on the surface is an important research topic in combination design and graph theory. The two embedding of complete graph K2mn+1 on the directional surface is a topological embedding of a surface 2- dyeing, and the first color class constitutes a s- circle, and the other color class constitutes a t- circle [2].Grannel et al. [11-13] to study when s = t= 3, that is, the two embedded.2010 years of the Steiner three unit (STS), Brown[7] constructs a class of two embeddedness, and this kind of two embedding makes s, t one equal to 3, the other equal to the concept of Heffter array that 4.Archdeacon[2] put forward in 2014. The two embedded.Heffter array of Steiner three is composed of two orthogonal Heffter systems, from combination design. In view, a Heffter system can construct a cyclic k- loop.Heffter array which is related to complete two partite graph Km, n traffic distribution. The flow graph satisfying certain conditions can be used to construct complete graph orientable embeddable. So, Heffter arrays can be used to construct a complete graph on the orientable surface for two embedding. In the same year, Archdeacon and Dinitz etc. Human [5] defines an integer Heffter matrix H (n; K) with an empty position. He proves that the necessary condition for the existence of H (n; K) is NK 0,3 (MOD 4) and conjectured that the condition is sufficient and constructs the construction of the two types of non empty spaces when the K is the even number and the 1 (4). Heffter arrays, that is, H (3, n) and H (5, n). Further, Boothby[6] demonstrated in his doctoral thesis that the non empty Heffter array exists when and only as m2, n2. this article mainly introduces the two embeddedness of Heffter array and graph, and constructs a number of integer Heffter squares with empty positions, which are divided into four chapters. The basic concepts and symbols. In the second chapter, the two embedded relationship between Heffter array and graph is introduced. The third chapter, on the basis of the integral Heffter matrix with the empty position in Archdeancon, constructs the integral Heffter square of some parameters with the empty position.

【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.2
，

本文编号：1800040