【作者】 张波；

【导师】 张和平；

【作者基本信息】 兰州大学 ， 数学， 2022， 硕士

【摘要】 设M是图G一个完美匹配.若M的子集S唯一包含在完美匹配M中,则称S是M的一个强迫集.M中最小强迫集的大小称作M的强迫数,记作f(G,M).图G所有完美匹配的强迫数所构成的集合叫做G的强迫谱,即Spec(G)={f(G,M)|M是G的完美匹配}.图G强迫谱中的最小值和最大值分别记作f(G)和F(G).六角系统H是一个2-连通平面二部图,其每个内面的边界是一个边长等于1的正六边形.H的Z-变换图Z(H)是以H的所有完美匹配为顶点集合,两个完美匹配在Z(H)中相邻,当它们的对称差是一个正六边形.设Hz是Z(H)有1度顶点的六角系统,sz是Z(Hz)中1度顶点对应完美匹配确定的六角形.根据Hz包含以sz为中心最大的凸六角系统O(m,m,m)和三角形六角系统T(k)对Hz进行分类,记作Hz(m,k),其中m≤k≤2m.最近,张雅娴等证明了特殊的凸六角系统O(m,m,m)的强迫谱是连续的,得到了六角系统Hz(m,k)的最小强迫数.本文的主要工作是研究Hz的强迫谱.本文在第二章证明了一般凸六角系统O(m,k,n)的强迫谱是连续的,在第三章我们得到了三角形六角系统T(m)的强迫谱是不连续的,特别地证明了强迫数F(T(m))-1?Spec(T(m)),当m是奇数时证明了其强迫谱仅缺失F(T(m))-1—个值,而当 m 是偶数时证明了[f(T(m)),F(T(m))]\{f(T(m))+1,F(T(m))-1}?Spec(T(m)),但尚未构造出T(m)的完美匹配使其强迫数等于f(T(m))+1,在第四章我们得到了一般Hz(m,k)强迫谱的部分结果:[f(Hz(m,k)),1/2k2+1/2k]\{m+1,1/2k2+1/2k-1}?Spec(Hz(m,k)),我们对两个缺失值{m+1,1/2k2+1/2k-1}进行了分析并给出了相关的猜想.更多还原

【Abstract】 Let M be a perfect matching of a graph G.A forcing set S for a perfect matching M of G is a subset of M such that it is contained in no other perfect matchings of G.The cardinality of a forcing set of M with the smallest size is called the forcing number of M,denoted by f(G,M).The forcing spectrum of G is defined as:Spec(G)={f(G,M)|M is a perfect matching of G}.The minimum and maximum values in the forcing spectrum of G are denoted as f(G)and F(G),respectivelyA hexagonal system H is a plane 2-connected graph,in which each inner face is a regular hexagon with side length 1.The Z-transformation graph Z(H)is the graph whose vertices are all perfect matchings of H and the two vertices are adjacent if and only if the symmetry difference of their corresponding perfect matchings is a hexagon.Let Hz be a hexagonal system with Z(H)containing a 1-degree vertex and sz be a hexagon determined by the perfect matching corresponding to the vertex of 1-degree in Z(Hz).If Hz includes maximum m)and T(k)with sz as the center,we will denote Hz as Hz(m,k)where m≤k≤2m.Recently,Zhang and Zhang proved that for a regular convex hexagonal system O(m,m,m),its forcing spectrum is continuous,and obtained the minimum forcing number of hexagonal system Hz(m,k).The main work of this paper is to study the forced spectrum of Hz.In this paper,firstly we prove that the forcing spectrum of convex hexagonal system O(m,k,n)is continuous.Secondly,we obtain that the forcing spectrum of T(nz)is discontinuous and in particular,F(T(m))-1?Spec(T(m));when m is odd,it is proved that its forcing spectrum is only missing value F(T(m))-1;when m is even,it is proved that[f(T(m)),F(T(m))]\{f(T(m))+1,F(T(m))-1}?Spec(T(m)),but a perfect matching of T(m)has not been constructed whose forcing number equal to f(T(m))+1.Finally,for general hexagonal system Hz(m,k),we prove that its forcing spectrum may be missing two values f(Hz(m,k)+ 1 and 1/2k2 +1/2k-1 in the range of[f(Hz(m,k)),1/2k2+1/2k].and give their relevant conjectures.更多还原