Characterization and linear-time recognition of balanced distance-hereditary graphs

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, we derive an explicit linear-time algorithm that decides balancedness within the class of distance-hereditary graphs and returns an induced $\overline{3K_2}$ when the input graph is not balanced.