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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.00730
curl -X POST /api/v1/records/arxiv/2607.00730/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.00730/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'