A note on distance-hereditary graphs whose complement is also distance-hereditary
Hugo Jacob · 2025
Read A note on distance-hereditary graphs whose complement is also distance-hereditary by Hugo Jacob (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12857.txt.
Introduction
Hugo Jacob writes a short 2025 mathematics note on a special family of graphs, those that break down fully under split decomposition. He asks which of them keep that property when every link is flipped, turning the graph into its complement. The note characterizes those graphs in two ways, through their split decomposition and through their modular decomposition. Two matching descriptions give researchers a firm grip on a narrow but tidy corner of graph theory.
Catalog record
| CREATOR | Hugo Jacob |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12857
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on distance-hereditary graphs whose complement is also distance-hereditary Hugo Jacob 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. Distance-hereditary graphs constitute a well-known hereditary 1 1 1 A class of graphs is hereditary if it is closed under induced subgraphs. class of graphs which admits many characterisations. Their name comes from their characterisation as graphs whose connected induced subgraphs preserve distances. They are also characterised by a simple list of forbidden induced subgraphs: holes, the house, the domino, and the gem (see Fig. 1 ). As such distance-hereditary graphs are also called HHDG-free graphs. They also admit a characterisation via a sequence of eliminations of twins 2 2 2 Two vertices u,v are twins if N(u)\setminus\{u,v\}=N(v)\setminus\{u,v\} . and pendant vertices 3 3 3 A pendant vertex is a vertex of degree 1 . . Finally, a graph is distance-hereditary if it is totally decomposable by the split decomposition. This last characterisation will be explained in further detail later. Figure 1. The forbidden induced subgraphs corresponding to the class of distance-hereditary. From left to right: holes (cycles of length at least 5 ), house, domino, and gem. The split decomposition was first introduced by Cunningham [ Cun82 ] . We give only a brief presentation to introduce some notations, see e.g. [ GP12 ] for a more detailed presentation. It is based on the notion of split. Given a graph G=(V,E) , a split is a bipartition (A,B) of V such that |A|,|B|\geq 2 and such that there are all edges between N(A) and N(B) . A split (A,B) is called strong if it does not overlap other splits (A^{\prime},B^{\prime}) , i.e. one of A\cap A^{\prime} , B\cap A^{\prime} , A\cap B^{\prime} , B\cap B^{\prime} must be empty. Decomposing using strong splits produces a unique decomposition which we call the (canonical) split decomposition. The split decomposition (T,\mu) of a graph G can be described via an undirected tree T whose leaves are bijectively mapped to V(G) . Each internal node t of T is labelled by an induced subgraph \mu(t) of G corresponding to picking a vertex 4 4 4 The choice is not arbitrary. in each subtree incident to t . The vertices of \mu(t) are thus in bijection with edges incident to t in T . We call interface vertex a vertex of some graph \mu(t) mapped to an edge of T not incident to a leaf. The strong splits of G correspond exactly to the bipartitions (A,B) of the set of leaves of T such that there is an internal edge e of T such that leaves in A are in the same component of T-e . The important property of the split decomposition is the following. Lemma 1 ( [ GP12 ] ) . Two vertices u,v\in V(G) are adjacent in G if and only if, for every internal node t of T on the path P between the leaves mapped to u and v , there is an edge in \mu(t) between the vertices of \mu(t) mapped to the edges on P . The following observation will be implicitly used to reason on the structure of split decompositions. Observation 1 . Internal nodes of a split decomposition have degree at least 3 . The fact that a distance-hereditary graph is totally decomposable by the split decomposition can be expressed more explicitly as follows. Theorem 1 ( [ GP12 ] ) . A connected graph G is distance-hereditary if and only if its split decomposition (T,\mu) has all its internal nodes t labelled by graphs \mu(t) that are stars or cliques. Some other hereditary classes related to distance-hereditary graphs can be characterised by the structure of their split decomposition. Theorem 2 ( [ GP12 ] ) . A connected graph G is a cograph if and only if its split decomposition (T,\mu) has all its internal nodes t labelled by graphs \mu(t) that are stars or cliques and there is an edge of T towards which all stars are pointing 5 5 5 A graph \mu(t) that is a star points in the direction of the edge e incident to t to which the center of the star is mapped. It points towards some node or edge of T if the path leading to it from t contains e . . We now briefly introduce the notion of module . A module in graph G=(V,E) is a subset M of V such that for every vertex v\in V\setminus M N(v)\cap M\in\{M,\varnothing\} . A module is trivial if it consists of a single vertex or the entire vertex set V . In particular, connected components and pairs of twins are modules. A graph is prime 6 6 6 While this word can also be used for graphs that do not admit splits, we will restrict its use to graphs that admit only trivial modules. (with respect to modules) if it has only trivial modules. A module M is strong if it does not overlap other modules, i.e. for every other module M^{\prime} we have M\cap M^{\prime}=\varnothing , M\subseteq M^{\prime} or M^{\prime}\subseteq M . The modular decomposition of a graph G is a rooted decomposition tree representing the family of strong modules of G . Vertices of G are mapped to the leaves and the set of leaves of (rooted) subtrees are exactly the strong modules. The internal nodes of this tree are labelled by a (quotient) graph which encodes the adjacency between the strong modules corresponding to its incident subtrees. It is well-known that cographs are exactly graphs whose modular decomposition is labelled only by cliques and independent sets (this corresponds exactly to the cotree). An asteroidal triple (AT) is a triple of vertices such that each pair of vertices is connected by a path avoiding the closed neighbourhood of the third vertex. Theorem 3 ( [ AJK+25 ] ) . A connected graph G is distance-hereditary and AT-free if and only if its split decomposition (T,\mu) has all its internal nodes t labelled by graphs \mu(t) that are stars or cliques and there is a path P of T towards which all stars that label nodes t\in V(T)\setminus P are pointing. We will now consider graphs that are distance-hereditary and whose complement is also distance-hereditary. It is direct from the forbidden induced subgraphs of the class of distance-hereditary graphs to obtain the forbidden induced subgraphs of its complementation closed subclass (see Fig. 2 ). We denote this subclass by DH \cap co-DH (the class of graphs G that are distance-hereditary and whose complement \overline{G} is also distance-hereditary). Figure 2. The forbidden induced subgraphs of DH \cap co-DH. From left to right: C_{5} , the House and its complement P_{5} , the Gem and its complement K_{1}+P_{4} . We obtain a characterisation of prime graphs of DH \cap co-DH and deduce a characterisation of graphs of DH \cap co-DH by the structure of their split decomposition or modular decomposition. Theorem 4 . If G is a prime graph in DH \cap co-DH, then it is P_{4} or the