竞赛图和有向二部图的有向二长路分解

发布时间：2018-06-17 15:57

  本文选题：路分解 + 竞赛图　； 参考：《新疆大学》2017年硕士论文

【摘要】：无向图G的一个分解就是图G=(V(G),E(G)的边不交子图的集合F使得∪_(F∈F)E(F)=E(G).如果集合F的元素都是路或者圈,那么就称它是图G的路分解或者圈分解.另外,如果集合F的元素全部都与一个图F同构,那么我们就称它是图G的F分解.Veblen[18]证明了一个图存在圈分解当且仅当图的所有顶点度数是偶数.关于图的分解的文章有很多,我们可以在文献[3]中了解有关图分解的定义和概念并且看到一些早期的结果.对于一个正整数k ≥ 2,图G的Pk分解是指把G的边集划分成k-1长路.分解的概念也可以应用到有向图D中,有向图D的分解是弧不交子图的集合.一个有向图D的(?)分解是指把它的弧集划分成k-1长有向路.特别地,图D的一个(?)分解就是把它的弧集划分成有向2长路.Thomassen[13-15]研究了当k ≥ 4时,图的Pk分解.然而,有向图(?)分解的刻画并不被大家所了解.近期,Diwan[5]首先研究了有向图的(?)分解.Diwan[5]刻画了不存在(?)分解的对称有向图.在本文中,我们完整刻画了存在(?)分解的竞赛图和有向二部图.这样就解决了Diwan在[5]中所提出的一个问题.
[Abstract]:One decomposition of an undirected graph G is the set F of the edge disjoint subgraph of a graph G ~ (n) such that F 鈭，

本文编号：2031603