論文

本文へのリンクあり
2022年2月1日

Tight Cuts in Bipartite Grafts I: Capital Distance Components

  • Nanao Kita

This paper is the first from a series of papers that provide a
characterization of maximum packings of $T$-cuts in bipartite graphs. Given a
connected graph, a set $T$ of an even number of vertices, and a minimum
$T$-join, an edge weighting can be defined, from which distances between
vertices can be defined. Furthermore, given a specified vertex called root,
vertices can be classified according to their distances from the root, and this
classification of vertices can be used to define a family of subgraphs called
{\em distance components}. Sebö provided a theorem that revealed a
relationship between distance components, minimum $T$-joins, and $T$-cuts. In
this paper, we further investigate the structure of distance components in
bipartite graphs. Particularly, we focus on {\em capital} distance components,
that is, those that include the root. We reveal the structure of capital
distance components in terms of the $T$-join analogue of the general
Kotzig-Lovász canonical decomposition.

リンク情報
arXiv
http://arxiv.org/abs/arXiv:2202.00192
URL
http://arxiv.org/abs/2202.00192v1
URL
http://arxiv.org/pdf/2202.00192v1 本文へのリンクあり
ID情報
  • arXiv ID : arXiv:2202.00192

エクスポート
BibTeX RIS