完全多部图K_n(t)的{K_3+e}分解(英文)

{K_3+e}-Decomposition of Complete Multigraphs K_n(t)

如果Kn(t)能分解成一族同构于G的边不交的子图的集合,那么称Kn(t)存在G 分解.讨论了当G是K3+e时,Kn(t)的G 分解的存在性并给出其充要条件是:参数n,t满足下列条件之一:(1)t为偶数且n 3;(2)t为奇数且n≡0,1(mod8).

The complete multigraphs K_n(t) is said to have a G-decomposition,if it is the union of edge disjoint subgraphs each isomorphic to G. In this paper, G-decomposition of K_n(t) where G is the triangle with attached edge is studied. Necessary and sufficient conditions are given for the G-decomposition of K_n(t). The graph K_n(t) can be decomposed into G if and only if one of following conditions holds:(1) n3, when t≡0(mod 2);(2) n≡0,1 (mod 8), when t≡1(mod 2).