Odd Cuts in Bipartite Grafts II: Structure and Universality of Decapital Distance Components

Abstract

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ász 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^{\prime }$ under which a decapital distance component with respect to root $r$ is also a decapital distance component with respect to root $r^{\prime }$. 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.