几类格子图的反强迫数

发布时间：2021-11-23 12:06

　　设图G是一个有限的简单连通图,E（G）和V（G）分别是G的边集和顶点集.独立边集M是G的一个完美匹配当且仅当V（G）中的点都是M-饱和的.M的反强迫数是指在图G中删去不在M中的边而使得剩余图有唯一完美匹配的边的最少数目.G的反强迫谱是指其所有完美匹配的反强迫数的集合.对应的,反强迫谱中最大和最小的整数被称为最大反强迫数和最小反强迫数（简称反强迫数）,分别记为F（G）和f（G）.梯子图Ln是路Pn和P2的笛卡尔积.第一章中我们简单介绍了有关格子图的相关研究背景和成果,给出了本文的一些基础概念和重要引理.第二章中我们给出了一个分解定理,将Ln分成两个片段,Ln的一个完美匹配的反强迫数是各个片段对应完美匹配的反强迫数之和.应用分解定理,我们得出了Ln的反强迫谱及其谱的连续性.通过反强迫数或水平匹配边数对Ln的所有完美匹配分类计数,得到了关于斐波那契数列的两个组合解释.第三章中首先通过将梯子图Ln变形得到了删边梯子图ILn-i和“L”型梯子图LLn-i,分类计算得到了删边梯子图的反强迫谱,进而得到了“L”型梯子图的反强迫数.过程中得到了斐波那契数列的一个组合解释.第四章中利用之前得到的结论,分... 

【文章来源】：西北师范大学甘肃省

【文章页数】：39 页

【学位级别】：硕士

【部分图文】：

图２．１梯子图??

图２．３?Ｌ９的一个堯美匹配及其对应分解??

图３．１删边梯于ｆｔｆＬｆ??

【参考文献】：
期刊论文
[1]梯子图完美匹配的反强迫谱与斐波那契数列[J]. 韩振云,王杰彬.  兰州工业学院学报. 2020(01)
[2]循环梯状图的完美匹配的反强迫谱与卢卡斯数列[J]. 姚海元,王杰彬,王旭.  西北师范大学学报(自然科学版). 2018(02)

博士论文
[1]关于一些图类的强迫与反强迫多项式的研究[D]. 赵爽.兰州大学 2018
[2]图的匹配强迫谱与匹配反强迫谱研究[D]. 邓凯.兰州大学 2016

硕士论文
[1]几类特殊图的反强迫谱的研究[D]. 王杰彬.西北师范大学 2018
[2]广义Sierpi（?）ski图的第一类Zagreb指标与四角链的反强迫数[D]. 梁志鹏.新疆大学 2016



本文编号：3513847