A note on distance-hereditary graphs whose complement is also distance-hereditary

2025/04/17 by Jacob, Hugo
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.12857

Abstract

Distance-hereditary graphs are known to be the graphs that are totally decomposable for the split decomposition. We characterise distance-hereditary graphs whose complement is also distance-hereditary by their split decomposition and by their modular decomposition.

Related

• An Exact Enumeration of Distance-Hereditary Graphs
• Split decomposition and graph-labelled trees: characterizations and fully-dynamic algorithms for totally decomposable graphs
• A Polynomial Kernel for Distance-Hereditary Vertex Deletion
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions