袁兰党,杨立保,谷丽彦,白占立
(1.河北师范大学 数学科学学院,河北省数学研究中心,河北 石家庄 050024;2.邢台学院 数学科学技术学院,河北 邢台 054001;3.河北师范大学 学报编辑部,河北 石家庄 050024)
组合设计是组合数学中的一个重要分支,主要研究满足不同条件的构造的存在性,广泛应用于计算机科学、编码密码中.图分解是传统的区组设计的推广,是将区组设计中完全图推广到有限简单图,其内容更加丰富,应用范围也更广泛.关于图分解的研究有几十年了,代表性文章参见文献[1-6],其中分别给出了星图K1,k、圈图Cn和六点八边图的图分解存在谱.本文旨在研究2个七点七边图的图分解,是将多重完全图分解为若干个两两不相交且同构的七点七边图的并,确定图分解的存在谱.先介绍相关的基本概念[5]和主要结构.
设λKv是顶点集为X的v阶λ重完全图.有限简单图G=(V,E)的图分解是图λKv的边分解B(称为区组集),其中B中的元素是Kv的子图且与G同构.该图分解记为G-GDλ(v)=(X,B).显然,G-GDλ(v)存在的必要条件为
v≥|V(G)|,λv(v-1)≡0(mod2|E|),λ(v-1)≡0(modd),
(1)
其中,d是V中各顶点的度的最大公因数.

有限简单图G的带洞图分解是图λKn,n,…,n的边分解A(称为区组集),其中A中的元素称为区组是Kn,n,…,n的子图且与G同构.该带洞图分解记为G-HD(nt)=(X,H,A),其中H={Xi|i=1,2,…,t}为洞集合.特殊地,若λ重完全(v+1)部图λK1,1,…,1,w亦可拆分为与G同构的图,则称其为洞长为w的不完全G-分解,记为G-IDλ(v+w,w).易见,G-GDλ(v+1)为G-IDλ(v+1,1).当λ=1时,以上记号中的下标λ通常省略.
本文研究2个含C5的七点七边图Di(1≤i≤2)的图分解(图1,图2),这些图的顶点标记为(a,b,c,d,e,f,g).

图1 七点……