支撑子图的存在性若干问题研究

Some problems on network design, code design, building design, file transfer in computer network, as well as gene classification in biology and protein interaction can be transformed into graph theory problems. Such as file transfer problem in computer networks can be converted into (g,f)-factorizations of graphs (or (g,f)-coloring); The problem on telephone network design can be converted into 1-factors (or P2-factors) of graphs. The project mainly investigates several graph theory problems with relation to computer science and network theory, which mainly includes: The existence of edge-disjoint (g,f)-factors in graphs; The existence of component factors in graphs, as well as the relationship with the parameters of graphs; Orthogonal factorizations of graphs, in which problem we solve some conjectures on orthogonal factorizations of graphs; Fractional ID-(g,f)- factor-critical graphs; Connected fractional factors of graphs, in which problem we solve mainly several conjectures and problems on connected fractional factors of graphs; Some parameters conditions for fractional (g,f,k)-critical graphs.

网络设计、编码设计、积木设计、计算机网络中的文件传输问题，生物学中基因的分类和蛋白质的相互作用等问题都可转化为图论问题。如计算机网络中的文件传输问题可转化为图的(g,f)-因子分解（或(g,f)-染色）来研究；电话网络设计问题可转化为研究图的1-因子（或P2-因子）。本项目主要研究与计算机科学和网络理论有关的几个图论问题，其中主要有：边不交的(g,f)-因子的存在性条件；图的分支因子存在性条件,以及与图的参数的关系；图的正交分数因子分解问题，解决关于图的正交因子分解的几个猜想；分数ID-(g,f)-因子临界图问题；图的连通分数因子，解决关于图的连通分数因子的猜想和问题；分数(g,f,k)-临界图与图的各种参数的关系。

图的因子理论是图论的重要研究分支，有着广泛的应用。例如：计算机网络中的文件传输问题可转化为图的(g, f ) -因子分解来研究；拉丁方块和空间方块的设计问题可转化为图的因子和正交因子分解来研究；通信网络中的一些问题可转化为图的因子和分数因子来研究。在国家自然科学基金项目(No.11371009)资助下，项目负责人和项目组成员主要完成了图的正交 (g, f ) -因子分解、有特定性质的图的分数(g, f ) -因子存在性条件、图中存在边不交因子、图的哈密顿(g, f )-因子和图的分支因子等几个方面内容的研究工作，获得了一些重要的研究成果，具体如下：1、证明了(0,mf -(m-1)r)-图、[0,k1+k2+…+km-n+1]-图、(mg+(k-1)r,mf -(k-1)r)-有向图、(0,mf –m+1)-有向图和(0,mf -(m-1)r)-有向图的正交因子分解的存在性。2、研究了图中边不交因子的存在性问题。3、得到图的分支因子、分支因子覆盖图和分支因子消去图的一些结论。4、给出了一个图是分数ID-k-因子临界图、分数ID-[a,b]-因子临界图、分数ID-(g, f ) -因子临界图的一些参数条件。5、研究了图的分数(g, f )-因子、分数(g, f )-消去图和分数(g, f, m )-消去图问题，并且得到若干新的充分条件。6、给出了一个图是(a, b, k)-临界图的一个新的独立集的邻集和最小度条件；给出了一个图是分数(g, f, k)-临界图的三个充分条件。7、给出了一个图是所有分数(a, b, k)-临界图的一个充要条件；证明了一个图是所有分数(a, b, k)-临界图的邻域并和联结数条件。8、得到了一个图有哈密顿(g, f )-因子的一个充分条件。9、获得一个图有k-哈密顿[a,b]-因子的稳定数条件、度条件、韧度条件和孤立韧度条件。