Decomposition of a graph into two disjoint odd subgraphs
Decomposition of a graph into two disjoint odd subgraphs
复制标题
将图分解为两个不相交的奇数子图
DOI：
10.1007/s00373-018-1970-0
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Gyula Katona and Kitti Varga
中科院分区：
文献类型：
--
作者：
Mikio Kano;Gyula Katona and Kitti Varga
重图中的奇（偶）子图是指每个顶点都有奇（偶）度的子图。我们说一个重图可以分解成两个奇子图，如果它的边集可以划分成两个集，使两者都形成奇子图。本文给出了多重图可分解为两个奇子图的一个充要条件。我们还提出了一个多项式时间算法找到这样的分解或显示其不存在。我们还处理的情况下，分解成一个偶数子图和一个奇数子图。
An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for thedecomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph.