{"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","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-01","reactions":{}}