完全图Kn的分解

顾成扬

顾成扬

（淮阴师范学院数学与统计学院，江苏，淮安 223300）

完全图K；完全二部图K；路P；圈C

0 引言

记K表示个顶点的完全图，K表示完全二部图，两个部分点集分别有和个顶点，P表示个顶点的路，C表示个顶点的圈。以下讨论的图均是无孤立点的简单图。

定义 设={1，2，…，F}是一族简单图，是图的一族边不相交的子图，若

1）的每一条边恰在的一个子图中出现；

2）任意∈，存在∈，使得与同构，则称为的一个-分解，进一步地，若任意∈，中至少有一个子图与同构，则称为的一个-强制分解。

注记1 当仅含一个子图时，称为的-分解，显然的一个-分解必定是的-强制分解。

注记2 完全图K的一个-分解也称为(,,1)-设计，完全二部图K,的-分解也称为(,,,1)二部-设计[1]。

注记3 当1,2, …,r分别为1,2,…,r个顶点的完全图时。K的一个-分解就是成对平衡设计(,,1)-PBD。其中={1,2,…,k}，特别地，K的一个K-分解就是平衡不完全区设计(,,1)-BIBD。

1 引理和记号

引理1[3]K存在5-分解的充分必要条件是≡0，1(mod 8)。

引理2[3]K存在5-分解的充分必要条件是≡1，5(mod 10)。

用表示路图5，用(a,b,c,d,e)表示圈图5（如图1和图2）。

图1 路图P5

图2 圈图C5

引理32,4和3,4的5-分解存在。

证明 记(2,4) ={1,2}∪{a,b,c,d},2,4的5-分解是：

5：

记(3,4) ={1,2,3}∪{a,b,c,d},3,4的P-分解是：

P：。

引理4K,4(≥2)的5-分解存在。

证明 因为完全二部图K,4(≥2)可以分解成完全二部图2,4和完全二部图3,4，所以K,4的5-分解存在，进一步还可以证明K,8(≥ 2,≥ 1为正整数)的P-分解存在。

5：<2,4,6,7,1><1,3,5,7,4><2,7,3,6,5><4,1,6,2,5>5：(1,2,3,4,5)

P：<0,1,8,2,6><0,2,7,1,6><6,3,0,4,8><8,3,7,4,6>

C：(1,2,5,3,4)(5,8,6,0,7)(1,3,2,4,5)(0,5,6,7,8)。

5：<2,1,4,9,7>（+2 mod 5）

5：(2,3,9,6,8)（+2 mod 5）。

图3 完全图K11的一个子图

5：<1,b,2,c,3><1,c,a,d,3>

5：(2,d,b,3,a)(1,d,c,b,a)

证明 记(12) ={1,2,…,12}，12可以分解成：1个8(顶点集为{1,2,…,8})，1个4,4(两个顶点集{1,2,3,4}和{9,10,11,12})和1个图4,4∪4（如图4）。

图4 完全图12的一个子图

Fig.4 A subgraph of complete graph12

P：<11,5,12,7,9><12,6,9,10,8><8,9,12,11,10>

C：(5,10,6,11,9)(10,7,11,8,12)

再由引理1和引理4知结论成立。

证明13可以分解成：1个5，1个8和1个5,8，由引理2、引理1和引理4知结论成立。

P：<11,9,13,10,14><11,10,12,9,14>

C：(1,8,14,13,12)(8,12,14,11,13)

再由引理8和引理4知结论成立。

证明15可以分解成1个7，1个8和1个7,8，由引理5、引理1和引理4知结论成立。

2 主要结果

证明 由引理1、引理2及定理1即可推得。

[1] Ushio K. G-designs and related designs [J]. Discrete Math., 1993,116:299-311.

[2] Bermond J C, Schonhei M J. G-decomposition of K, wherehas four vertices or less[J].Discrete Math.,1977,19:113-120.

[3] Bermond J C, Huang C, Rosa A, et alDecomposition of complete graphs into isomorphic sutgraphs with fivevertices[J]. Ars Combinatorics,1980,10:293-318.

[4] Yamamoto S, Ikeda H, Shige-eda S, et al. On claw-decomposition of complete graphs and complete bipartite graphs [J]. Hiroshima Math. J., 1975,5: 33-42.

[5] Abueida Atif A, Daven Mike. Multidesign for graph-pairs of order 4 and 5[J].Graphs and Combinatorics, 2003, 19(4): 433-447.

[6] He Q F. Study on paths and stars of several classes of graphs decomposed into edge inequalities[D]. Zhengzhou: Zhengzhou University,2019.

[7] Hou N C. Path and star decomposition of complete graphs[D]. Shanghai:East China Normal University,2022.

[8] Ilayaraja M, Sowndhariya K, Muthusamy A.Decomposition of product graphs into paths and stars on five vertices[J]. AKCE International Journal of Graphs and Combinatorics, 2020,17(3):1-7.

[9] Daniel Horsley, Rosalind A Hoyte. DecomposingK+w-Kinto cycles of prescribed lengths[J]. Discrete Mathematics, 2017,340(8):1818-1843.

[10] Jeevadoss S, Muthusamy A. Decomposition of complete bipartite graphs into paths and cycles[J]. Discrete Mathematics, 2014(331):98-108.

[11] Shyu Tay Woei. Decomposition of complete graphs into cycles and stars[J]. Graphs and Combinatorics,2013(2): 301-313.

[12] Shyu Tay Woei. Decomposition of complete bipartite graphs into paths and stars with same number of edges[J]. Discrete Mathematics, 2012(7):865-871.

[13] Tay-Woei Shyu. Decomposition of complete graphs into paths and stars[J]. Discrete Mathematics,2010(15-1): 2164-2169.

[14] Benjamin R S. Decomposing complete equipartite graphs into cycles of length 2p[J]. Journal of Combinatorial Designs, 2008 (3):244-252.

[15] 顾成扬.完全图K和完全多部图K()的{3,4}-分解强制分解[J].淮阴师范学院学报:自然科学版,2002,1(3):6-9.

[16] 顾成扬.完全图K的{4,4,4}-分解[J].华侨大学学报,2005,26(2):222-224.

[17] 顾成扬.完全图K分解成五个顶点的星和圈[J].淮阴师范学院学报:自然科学版,2007,6(1):14-16.

[18] 彩春丽,陶黄林,彭嘉昊.围长至少为5的平面的线性着色[J].井冈山大学学报:自然科学版,2021,42(3):8-11,19.

GU Cheng-yang

（School of Mathematics and Statistics, Huaiyin Normal University, Huai’an, Jiangsu 223300, China）

complete graphsK; complete bipartite graphsK,n; pathP; cycleC

1674-8085（2023）05-0011-04

O157.5

A

10.3969/j.issn.1674-8085.2023.05.003

2022-05-29；

2022-07-05

国家自然科学基金项目(12271200)

顾成扬(1964-)，男，江苏淮安人，副教授，主要从事组合设计、图分解等研究(E-mail:525290408＠qq.com,gcy@hytc.edu.cn).