惠志昊
(平顶山学院数学与信息科学学院 平顶山 467000)
步长为1和4的循环图的k-偶匹配可扩性∗
惠志昊
(平顶山学院数学与信息科学学院 平顶山 467000)
称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C2n(1,4)的k-偶匹配可扩性。
完美匹配;偶匹配可扩;k-偶匹配可扩;循环图
设图G是一简单的且有完美匹配的连通图。称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(|V(G)|-2)2)的偶匹配M 都可以扩充为G的一个完美匹配。本文中没有加以说明的概念和术语可参考[1],关于图的匹配可扩性和k-偶匹配可扩性已经有很多结论[3~11]。在文献[7]中证明了判定图G是否含有基数是k的偶匹配是NP-困难问题;判定图G是否是偶匹配可扩的是co-NP-困难问题。本文主要根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性。这对我们进一步判定偶匹配可扩图有很重要的意义。
定义1 对一个有 2n 个顶点 x0,x1,x2,…, x2n-1的图G,如果 xixj是图G的边,当且仅当i-j≡±1(mod2n),或者 i-j≡±k(mod2n),则称图 G为步长为1和 k 的循环图,记为 C2n(1,k)[2]。
令 Zn为模 n的剩余类加群,即Zn={0,1,2,…,n-1}运算取模 n的加所构成的群。若S⊆Zn-{0},且S=-S,则称S为Zn的特征集。若 S 为 Zn的特征集,则有 j1,j2,j3,…,jr⊆{1,2,…,[n 2]} ,S={j1,j2,j3,…,jr,n-j1,n-j2,n-j3,…,n-jr},其中[n 2]表示不超过n 2的最大整数。
定义 2[2]对上述 Zn,S ,若图 G=(V,E)满足点集V(G)=Zn,边集 E(G)={(i,j)|j-i∈S},则称 G为Zn上关于特征集S的循环图,记为Cn(j1,j2,j3,…,jr) ,其 中 j1<j2<j3<…<jr,并 称j1,j2,j3,…,jr为生成元。
引理1[1](Tutte定理) 图G中存在完美匹配,当且仅当对于任意的S⊆V(G),ο(G-S)≤ ||S,其中ο(G)表示G的奇分支数。
引理2[3]图G是偶匹配可扩的,当且仅当对于 G的任意偶匹配 M 的 S⊆V(G)V(M),有ο(G-V(M)-S)≤ ||S 。……