Pk(Mk)-等可覆蓋的路和圈.pdf

1、設G為v階簡單圖，H為G的一個不帶孤立點的子圖.圖G的一個H-覆蓋，是指一個有序對（V,(B)），其中V為G的點集，(B)為G的一些子圖（亦稱為區(qū)組）構成的集合，使得任一區(qū)組均與圖H同構，且G的任意兩個不同點組成的邊至少在(B)的一個區(qū)組中出現(xiàn).(V)B∈(B)，若(B)\{(B)}都不是G的一個覆蓋，則稱（V,(B)）為G的一個極小H-覆蓋.一個圖覆蓋稱為是最小的，如果不存在其它含有更少區(qū)組個數(shù)的覆蓋.若G的每個極小H-覆蓋都是G的最

2、小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-

3、等可覆蓋的當且僅當n=2k，2k+1.
　　 記λKv為λ重v階完全圖.若λKv的邊集可以拆分成兩兩不交的m長圈的集合，則稱這些圈構成一個m-圈系統(tǒng)，記作m-CS(v，λ).如果一個m-CS(v，λ)中的所有圈可以被分拆為一些α-平行類，則稱其為α-可分解的.本文第二部分采用直接構造與遞歸構造相結合的方法，研究α-可分解的圈系統(tǒng)的存在性問題，主要討論了m=8時的情況，并給出了α-可分解的frame的一些結果:
　　 1.