2025/03/31 by Kita, Nanao
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.23973
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' 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.