完全二部有向图的拟2k-因子分解

陆健，朱莉

（南通职业大学基础部，江苏南通 226007）

陆健，朱莉

（南通职业大学基础部，江苏南通 226007）

完全二部有向图；有向圈；因子分解；拟因子分解

0 引言

G（V，E）表示无向图，其中V是点集，E是边集。G*表示对称的有向图，它是由G的每条边替换成方向相反的两条有向弧而得到的有向图。如果G（或G*）的子图F包含了G（或G*）的所有的点，则称F为G（或G*）的生成子图。设H是G（或G*）的小子图，G（或G*）的H-因子是它一个生成子图F，其中F的每个分支都同构于H。如果G（或G*）的边集（或有向弧集）可以划分为G（或G*）的H-因子的和，则称G（或G*）存在H-因子分解，或称G（或G*）可H-因子分解。

图的因子分解问题是图论中的基本问题。因子分解问题的一个推广是图的拟因子分解。设x是G（或G*）的一个点，如果G（或G*）的子图F包含了G（或G*）中除x外的所有点，则称F为G（或G*）的一个拟生成子图。G（或G*）的拟H-因子是它一个拟生成子图F，其中F的每个分支都同构于H。如果G（或G*）的边集（或有向弧集）可以划分为G（或G*）的拟H-因子的和，则称G（或G*）存在拟H-因子分解，或称G（或G*）可拟H-因子分解。

1 ?k-因子分解研究现状

2 定理1.5 的证明

3 定理1.6 的证明

4 结束语

对称的完全二部有向图K*m，n存在2k-因子分解和拟k-因子分解，本文针对这个具体问题深入分析，采用最合适的方法——直接构造法，得出对应的充分必要条件，并给出了严格的理论推导。研究这类问题不仅具有理论意义，而且在计算机网络设计中也有一定的现实意义。

[1]Bennett FE,Sotteau D.Almost resolvable decompositions of Kn[J].J Combin Theory B,1981(2):228-232.

[2]Bennett FE,Z.Xuebin,Resolvable Mendelsohn designs with block size 4[J].Aequationes Math,1990(4):248-260.

[3]Ge G,Zhu L.Existence of almost resolvable 5-cycle systems[J].Aust J Comb,1995(3):181-196.

[4]Fu CM,Fu HL,Milici S,et al.Almost resolvable directed 2r-cycle systems[J].J.Combin.Designs,1995(1):443-447.

LU Jian,ZHU Li (Department of Basic Courses,Nantong Vocational College,Nantong 226007,China)

In combination with the direct construction method,this article puts forward the sufficient and necessary conditions for the existence of the2k-factorization as well as the neark-factorization of the symmetric complete bipartite diagram K*m，n,which is of certain theoretical significance.

Complete bipartite digram;Directed cycle;Factorization;Near factorization

O151.24

A

1671-9891（2014）04-0059-03

10.3969/j.issn.1671—9891.2014.04.016

2014-09-10

南通职业大学高等教育教改研究青年专项课题“数学基础课如何提升高职学生数学应用能力的研究与实践”（项目编号：2013-QN-02）；南通职业大学院级课题“以高数竞赛为平台提升高职学生数学应用能力的研究”（项目编号：1307311）。

陆健（1979—），男，江苏南通人，南通职业大学基础部讲师，硕士。