双部分嫁接中奇割的II:去首距离分量的结构与普适性
Odd Cuts in Bipartite Grafts II: Structure and Universality of Decapital Distance Components
摘要 Abstract
本文是关于双部分嫁接中\( T \)-割最大装填问题系列论文的第二篇,延续了第一篇(北村直树,“双部分嫁接中紧缩割I:资本距离分量”,{arXiv:2202.00192v2}, 2022)的工作。给定一个嫁接\((G, T)\),最小连接\( F \)以及称为根的指定顶点\( r \),嫁接\((G, T)\)的距离分量被定义为由\( F \)诱导的距离所确定的\( G \)的子图。如果一个距离分量包含根,则称其为“资本”;否则称为“去首”。在我们的第一篇论文中,我们研究了双部分嫁接中资本距离分量的典型结构,该结构可以用嫁接版本的Kotzig–Lovász分解来描述。在本文中,我们提供了去首距离分量的对应结构。我们还建立了两个顶点\( r \)和\( r' \)的一个必要且充分条件,使得关于根\( r \)的去首距离分量也是关于根\( r' \)的去首距离分量。由此得出结论,在双部分嫁接中,遍历所有根的选择时,去首距离分量的总数等于嫁接最小连接中边数的两倍。
This paper is the second in a series of papers characterizing the maximum packing of \( T \)-cuts in bipartite grafts, following the first paper (N.~Kita, ``Tight cuts in bipartite grafts~I: Capital distance components,'' {arXiv:2202.00192v2}, 2022). Given a graft $(G, T)$, a minimum join $F$, and a specified vertex $r$ called the root, the distance components of $(G, T)$ are defined as subgraphs of $G$ determined by the distances induced by $F$. A distance component is called {\em capital} if it contains the root; otherwise, it is called {\em decapital}. In our first paper, we investigated the canonical structure of capital distance components in bipartite grafts, which can be described using the graft analogue of the Kotzig--Lov\'asz decomposition. In this paper, we provide the counterpart structure for the decapital distance components. We also establish a necessary and sufficient condition for two vertices $r$ and $r'$ under which a decapital distance component with respect to root $r$ is also a decapital distance component with respect to root $r'$. As a consequence, we obtain that the total number of decapital distance components in a bipartite graft, taken over all choices of root, is equal to twice the number of edges in a minimum join of the graft.