Parity Factors I: General Kotzig-Lov\'asz Decomposition for Grafts
Parity Factors I: General Kotzig-Lov\'asz Decomposition for Grafts
复制标题
奇偶校验因子 I：移植物的一般 Kotzig-Lovasz 分解
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nanao Kita
中科院分区：
文献类型：
--
作者：
Nanao Kita
本文是第一个从一系列的论文，建立了基数最小连接在嫁接的basilica分解的推广。嫁接中的连接也被称为图中的$T$-连接，其中$T$是给定的顶点集，嫁接中的最小连接可以被认为是根据奇偶性提供的图中完美匹配的泛化。basilica分解是适用于具有完美匹配的一般图的正则分解，而一般Kotzig-Lov\'asz分解是构成该理论的三个中心概念之一。经典的kotzeg - lov 'asz分解是一类特殊的图的正则分解，被称为{\em因子连通图}，并以其对匹配多面体和晶格的研究的贡献而闻名。一般Kotzig-Lov\ asz分解是其经典对应的非平凡推广，适用于具有完美匹配的一般图。作为basilica分解理论的一个组成部分，一般的kotzeg - lov \'asz分解对匹配理论的进一步结果的推导做出了贡献，例如障碍的表征或紧切引理的替代证明。在本文中，我们给出了一般Kotzig-Lov\'asz分解在接枝中最小连接的类比。
This paper is the first from a series of papers that establish a generalization of the basilica decomposition for cardinality minimum joins in grafts. Joins in grafts are also known as $T$-joins in graphs, where $T$ is a given set of vertices, and minimum joins in grafts can be considered as a generalization of perfect matchings in graphs provided in terms of parity. The basilica decomposition is a canonical decomposition applicable to general graphs with perfect matchings, and the general Kotzig-Lov\'asz decomposition is one of the three central concepts that compose this theory. The classical Kotzig-Lov\'asz decomposition is a canonical decomposition for a special class of graphs known as {\em factor-connected graphs} and is famous for its contribution to the study of the matching polytope and lattice. The general Kotzig-Lov\'asz decomposition is a nontrivial generalization of its classical counterpart and is applicable to general graphs with perfect matchings. As a component of the basilica decomposition theory, the general Kotzig-Lov\'asz decomposition has contributed to the derivation of further results in matching theory, such as a characterization of barriers or an alternative proof of the tight cut lemma. In this paper, we present an analogue of the general Kotzig-Lov\'asz decomposition for minimum joins in grafts.