Id: arxiv/2607.00730 Url: https://arxiv.org/abs/2607.00730 Tags: math.CO, cs.DM Score: 0 Title: Characterization and linear-time recognition of balanced distance-hereditary graphs Domain: math.CO Source: arxiv Authors: Lucía Busolini, Guillermo Durán, Martín D. Safe Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-01 Page: https://delphi.science/r/arxiv/2607.00730 A graph is balanced if its clique-matrix contains no square submatrix of odd order with exactly two $1$'s in each row and in each column. Although it is known that a graph is balanced if and only if it contains no induced extended odd sun, a characterization of balanced graphs by minimal forbidden induced subgraphs is still unknown. In this work, we prove that, within the class of distance-hereditary graphs, balanced graphs are exactly the hereditary clique-Helly graphs. Equivalently, they are characterized by a single forbidden induced subgraph, namely $\overline{3K_2}$. From this result,…