论文部分内容阅读
设G为v阶简单图,H为G的一个不带孤立点的子图.图G的一个H-覆盖,是指一个有序对(V,(B)),其中V为G的点集,(B)为G的一些子图(亦称为区组)构成的集合,使得任一区组均与图H同构,且G的任意两个不同点组成的边至少在(B)的一个区组中出现.(V)B∈(B),若(B){(B)}都不是G的一个覆盖,则称(V,(B))为G的一个极小H-覆盖.一个图覆盖称为是最小的,如果不存在其它含有更少区组个数的覆盖.若G的每个极小H-覆盖都是G的最小H-覆盖,则称G是H-等可覆盖的.本文第一部分主要研究Pk-等可覆盖的路和圈及Mk-等可覆盖的路和圈的特征,给出了如下结果:
1.路Pn是Pk-等可覆盖的当且仅当n=k,k+1,…,2k-1,2k,3k-1.
2.圈Cn是Pk-等可覆盖的当且仅当n=k-1+x(1≤x≤(「)k+1/2」),2k-1,k≥4.
3.路Pn是Mk-等可覆盖的当且仅当n=2k+1.
4.圈Cn是Mk-等可覆盖的当且仅当n=2k,2k+1.
记λKv为λ重v阶完全图.若λKv的边集可以拆分成两两不交的m长圈的集合,则称这些圈构成一个m-圈系统,记作m-CS(v,λ).如果一个m-CS(v,λ)中的所有圈可以被分拆为一些α-平行类,则称其为α-可分解的.本文第二部分采用直接构造与递归构造相结合的方法,研究α-可分解的圈系统的存在性问题,主要讨论了m=8时的情况,并给出了α-可分解的frame的一些结果:
1.α-可分解的8-CS(v,λ)存在的必要条件也是充分的,除去v≡4,6,12,14(mod16),以及v≡15(mod16)(v非素数)的可能情形.
2.当g≡0(mod2)时,存在型为g3的(g,1,g/2)-圈frame.