论文部分内容阅读
无向图G的一个分解就是图G=(V(G),E(G))的边不交子图的集合F使得UF∈FE(F)=E(G).如果集合F的元素都是路或者圈，那么就称它是图G的路分解或者圈分解.另外，如果集合F的元素全部都与一个图F同构，那么我们就称它是图G的F分解. Veblen[18]证明了一个图存在圈分解当且仅当图的所有顶点度数是偶数.关于图的分解的文章有很多，我们可以在文献[3]中了解有关图分解的定义和概念并且看到一些早期的结果.对于一个正整数k≥2,图G的凡分解是指把G的边集划分成k-1长路.分解的概念也可以应用到有向图D中，有向图D的分解是弧不交子图的集合.一个有向图D的→Pk分解是指把它的弧集划分成k-1长有向路.特别地，图D的一个→P3分解就是把它的弧集划分成有向2长路. Thomassen[13-15]研究了当k≥4时，图的→P3分解.然而，有向图宫分解的刻画并不被大家所了解.近期，Diwan[5]首先研究了有向图的其分解. Diwan[5]刻画了不存在→P3分解的对称有向图.在本文中，我们完整刻画了存在P3分解的竞赛图和有向二部图.这样就解决了Diwan在[5]中所提出的一个问题.