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

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

2、小H-覆蓋，則稱G是H-等可覆蓋的.本文第一部分主要研究Pk-等可覆蓋的路和圈及Mk-等可覆蓋的路和圈的特征，給出了如下結(jié)果:
　　 1.路Pn是Pk-等可覆蓋的當(dāng)且僅當(dāng)n=k，k+1，…，2k-1，2k，3k-1.
　　 2.圈Cn是Pk-等可覆蓋的當(dāng)且僅當(dāng)n=k-1+x(1≤x≤(「)k+1/2」)，2k-1，k≥4.
　　 3.路Pn是Mk-等可覆蓋的當(dāng)且僅當(dāng)n=2k+1.
　　 4.圈Cn是Mk-

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