亏一k-可扩图的相关性质研究

发布时间：2018-06-09 02:18

  本文选题：匹配 + 亏一k-可扩　； 参考：《兰州大学》2017年硕士论文

【摘要】：设图G是一个顶点个数为n ≥ 2κ+ d + 2的连通图,其中κ, d是非负正整数并且n - d≡0 (mod 2).如果一个匹配覆盖了连通图中除d个顶点以外的所有顶点,那么称这个匹配是亏d匹配.如果G中的任意κ条独立边都包含在一个亏d匹配中,那么称图G是(0,k,d)-图.特别地,如果d = 0,图G是k-可扩图;如果d= 1,图G是亏一κ-可扩图.在本文中,我们首先考虑了 k-可扩图和亏一κ-可扩之间的关系,并且对亏一 k-可扩图进行了归类,表明当k ≥ 2时,亏一 κ-可扩图或者是二部图或者是因子临界图或者它的连通度是1.其次对亏一κ可扩图的曲面嵌入进行了讨论,证明了对于任意的正整数k,总存在可平面的亏一κ-可扩图;另外,对于最小度δ ≥ κ + 1且围长g ≥ 4的亏一 k-可扩图,我们给出了一般曲面嵌入的界(?) ,其中x(Σ)是曲面∑的欧拉示性数,μ'(0,∑,1)表示最小的正整数κ,使得任意亏一κ-可扩图都不能嵌入到曲面∑上.接下来,我们刻画了所有的极小亏一1-可扩二部图,并由此找到了亏一 k-可扩二部图的一类支撑树.最后本文解决了G□K2的可扩性问题,当G是亏一 1-可扩图时,G□K2是(0,3,2)-图;当G是亏一κ-可扩图时,κ≥2,G□K2是(0,4,2)-图;并且证明了这些结果都是紧的.
[Abstract]:Let G be a connected graph with the number of vertices n 鈮，

本文编号：1998358