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

Hugo Jacob

arxiv: 2504.12857 · v2 · submitted 2025-04-17 · 🧮 math.CO · cs.DM

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

Hugo Jacob This is my paper

Pith reviewed 2026-05-22 19:42 UTC · model grok-4.3

classification 🧮 math.CO cs.DM

keywords distance-hereditary graphssplit decompositionmodular decompositiongraph complementsgraph characterizationhereditary properties

0 comments

The pith

Distance-hereditary graphs whose complements are also distance-hereditary are characterized by their split and modular decompositions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a characterization of distance-hereditary graphs that remain distance-hereditary after taking the complement. It provides descriptions of these graphs in terms of their split decomposition and their modular decomposition. A reader would care because the result gives a concrete structural handle on a subclass of graphs with preserved distance properties, building directly on the known total decomposability of distance-hereditary graphs under split decomposition. This allows precise identification of when both a graph and its complement belong to the class.

Core claim

Distance-hereditary graphs whose complement is also distance-hereditary can be characterised by their split decomposition and by their modular decomposition.

What carries the argument

Split decomposition, which totally decomposes distance-hereditary graphs into simpler parts while preserving the property, together with modular decomposition applied to the same graphs and their complements.

If this is right

The graphs in question admit a complete structural description via decomposition trees from split and modular operations.
Recognition of such graphs reduces to checking the form of these decompositions.
The class is closed under the operations that preserve the decomposability conditions in both the graph and its complement.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The characterization may extend to related graph classes that admit similar total decompositions, such as certain cographs or other distance-preserving families.
Algorithmic consequences could include linear-time recognition procedures that exploit the decomposition trees directly.
Connections to other complement-closed properties in graph theory become testable once the decomposition forms are fixed.

Load-bearing premise

The characterization depends on the background fact that distance-hereditary graphs are exactly the graphs that are totally decomposable under split decomposition.

What would settle it

A concrete counterexample would be any distance-hereditary graph whose complement is also distance-hereditary but whose split decomposition or modular decomposition fails to match the patterns described in the characterization.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This is a short, clean structural note that pins down exactly which distance-hereditary graphs have distance-hereditary complements via their split and modular decompositions.

read the letter

The main takeaway is that the paper gives an explicit description of distance-hereditary graphs with distance-hereditary complements by inspecting the possible forms of their split decomposition trees and modular decompositions. It starts from the standard fact that distance-hereditary graphs are precisely the totally split-decomposable ones, then checks which combinations of join and union operations on the modules keep the complement inside the same class. That is the actual content delivered. The work is straightforward and stays within the existing decomposition framework without introducing new machinery or claiming broader consequences. The argument appears to cover the cases without obvious gaps once the background theorem is granted, and the modular-decomposition view adds a second, independent way to see the same restriction. The main limitation is scope: this is a narrow observation inside one corner of graph theory, and it does not resolve any long-standing open question or supply new algorithmic tools. The proofs are presumably short and case-based, which fits the “note” format but means the result stands or falls on whether the case analysis is exhaustive. For readers already working with split or modular decompositions of distance-hereditary graphs, the note supplies a useful reference point. For anyone outside that small community the paper offers little. It is the sort of incremental structural result that belongs in a specialized journal or as a short communication rather than a flagship paper. I would send it to peer review so that the case analysis can be checked in detail; the claim is modest enough that a referee can verify it without excessive effort.

Referee Report

0 major / 4 minor

Summary. The manuscript characterizes distance-hereditary graphs whose complements are also distance-hereditary. It does so via two equivalent descriptions: one in terms of the allowed forms of the split decomposition tree (building on the known fact that distance-hereditary graphs are precisely the totally split-decomposable graphs) and one in terms of the modular decomposition. The note isolates the admissible configurations of join and union operations on modules under which the complement remains distance-hereditary.

Significance. If the characterizations are correct, the paper supplies a clean structural description of this subclass, which may support algorithmic recognition or enumeration results. The work correctly invokes the standard background theorem on split decomposability and performs a case analysis on decomposition trees without introducing circularity or hidden assumptions. This is a modest but useful contribution to the structural theory of hereditary graph classes.

minor comments (4)

Abstract: the phrase 'totally decomposable for the split decomposition' is slightly nonstandard; replacing it with 'totally split-decomposable' would align better with the literature cited in §2.
§2: the recall of the split decomposition could usefully include a pointer to the original Cunningham-Edmonds reference for readers unfamiliar with the background theorem.
§4 (modular decomposition characterization): the statement that the quotient must be a path or cycle of length at most 4 is clear, but adding one or two small illustrative examples would improve readability.
Figure 1: the decomposition tree diagram would benefit from explicit labels on internal nodes indicating whether each split is a join or a union.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The summary accurately captures our use of split decomposition (building on the total split-decomposability of distance-hereditary graphs) and modular decomposition to characterize the subclass whose complements are also distance-hereditary.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's characterization of distance-hereditary graphs whose complements are also distance-hereditary relies on the standard external theorem that distance-hereditary graphs are precisely the totally split-decomposable graphs. This background fact is invoked as an independent premise rather than derived or fitted within the paper itself. The note then examines configurations of the decomposition trees (split and modular) to isolate cases where the complement remains distance-hereditary, without any self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations that reduce the central claim to its own inputs. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on one background theorem about split decomposability of distance-hereditary graphs and on the definitions of modular and split decompositions. No free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Distance-hereditary graphs are exactly the graphs that are totally decomposable for the split decomposition.
Invoked in the first sentence of the abstract as the starting point for the characterization.

pith-pipeline@v0.9.0 · 5544 in / 1190 out tokens · 25069 ms · 2026-05-22T19:42:01.367047+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

A connected graph G is distance-hereditary if and only if its split decomposition (T, µ) has all its internal nodes t labelled by graphs µ(t) that are stars or cliques. (Theorem 1)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.