⚛️ quantum physics

Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions

This paper extends Bouchet's results on local complement equivalence classes by using split decomposition to derive explicit formulas for the sizes of these classes in broad families of distance-hereditary graphs, including complete multipartite graphs, clique-stars, and repeater graphs.

Original authors: Nicholas Connolly, Shin Nishio, Kae Nemoto

Published 2026-03-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicholas Connolly, Shin Nishio, Kae Nemoto

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a group of friends sitting around a table. You decide to play a game called "The Neighborhood Flip."

Here are the rules:

You pick one person (let's call them Alex).
Look at everyone Alex is currently friends with (Alex's "neighborhood").
Flip the friendships: If two people in Alex's neighborhood were friends, they are now strangers. If they were strangers, they are now best friends.
Alex's own friendships don't change, and friendships between people outside Alex's neighborhood stay exactly the same.

You can do this flip with anyone in the group, as many times as you want.

The Big Question

If you start with a specific group of friends and keep flipping neighborhoods, you will generate a huge collection of different friendship maps. The big question this paper asks is: "How many unique friendship maps can we possibly create from one starting group?"

In the world of mathematics, this is called finding the size of a "Local Complement Orbit."

The Problem

For a small group of 5 or 6 people, you can just sit down and count them. But as the group gets bigger, the number of possible maps explodes. It grows so fast that even supercomputers can't count them all for a group of 20 people. It's like trying to count every possible arrangement of a deck of cards by shuffling them one by one; you'd be here forever.

The Solution: The "Tree of Truth"

The authors of this paper didn't try to count every single map. Instead, they found a clever shortcut using a tool called Split Decomposition.

Think of a complex friendship group not as a messy web, but as a family tree.

Some parts of the group are tightly knit (like a clique where everyone knows everyone).
Some parts are like a star (one popular person connected to many others who don't know each other).
The "Split Decomposition" breaks the whole graph down into these simple, building-block pieces (called Quotient Graphs).

The magic discovery of this paper is this: When you do the "Neighborhood Flip" game, the structure of the family tree never changes. The tree stays the same; only the specific "flavor" of the building blocks (the cliques or stars) changes slightly.

The Analogy: LEGO Sets

Imagine your graph is a LEGO castle.

The Split Decomposition is the instruction manual that tells you the castle is made of a specific set of bricks: 3 red 2x4 bricks, 2 blue 1x2 bricks, and 1 yellow 2x2 brick.
Local Complementation is like taking those specific bricks and repainting them or swapping their internal patterns, but never changing the fact that you have 3 red bricks and 2 blue ones.

The paper says: "Instead of counting every possible castle you can build, let's just count how many ways we can arrange the types of bricks allowed by the manual."

What They Actually Did

The researchers focused on a special, highly symmetrical family of graphs called Distance-Hereditary Graphs. These are graphs where the "distance" between any two people stays the same even if you remove other people from the group. (Think of a tree structure or a perfect circle).

They took three specific types of these graphs and solved the counting puzzle:

Complete Multipartite Graphs: Imagine several groups of people where everyone in Group A is friends with everyone in Group B, but no one in Group A is friends with anyone else in Group A.
Clique-Stars: A central group of friends (a clique) surrounded by several other groups, where the central group is friends with everyone else, but the outer groups don't talk to each other.
Repeater Graphs: A central hub with "leaves" (single friends) hanging off it, often used in quantum physics.

Why Should You Care? (The Quantum Connection)

You might wonder, "Who cares about counting friendship maps?"

In the real world, this isn't just about math; it's about Quantum Computers.

In quantum physics, information is stored in "Graph States."
The "Neighborhood Flip" game is actually a real physical operation that scientists can perform on quantum computers (using single-qubit gates).
If you want to build a quantum computer, you need to know: "What is the simplest, most efficient way to arrange these quantum bits?"

By knowing exactly how many different "friendship maps" (or quantum states) are equivalent to each other, scientists can find the best version of a quantum network. They can find the one that uses the least amount of energy or is most resistant to errors (like a photon getting lost in a fiber optic cable).

The Takeaway

This paper is like finding a master key for a very complex lock.

Before: We knew the lock was hard to open, and we could only guess the size of the room inside for very small locks.
Now: The authors found a way to look at the "blueprint" (the Split Decomposition) of the lock. They proved that for a huge family of locks (Distance-Hereditary graphs), we can calculate the exact size of the room inside using simple formulas.

They didn't just count the rooms; they also showed you exactly how to walk from one room to another (the sequence of flips) and identified which room is the most efficient to live in (the one with the fewest connections).

In short: They turned a chaotic, impossible-to-count mess into a neat, predictable pattern, helping us build better quantum computers along the way.

1. Problem Statement

The paper addresses the problem of determining the size of Local Complement (LC) equivalence classes (also known as LC orbits) for graphs.

Local Complement: An operation introduced by Bouchet that replaces the neighborhood of a chosen vertex with its edge-complement. Two graphs are locally equivalent if one can be transformed into the other via a sequence of local complements.
The Challenge: Determining the size of an LC orbit is generally #P-complete. While explicit formulas exist for simple cases like paths and cycles, and brute-force enumeration works for very small graphs (up to 9 vertices), no general formula exists for arbitrary graphs.
Motivation: This problem is critical in Quantum Information Theory. Graph states (quantum states represented by graphs) are central to measurement-based quantum computation. Single-qubit Clifford operations on these states correspond exactly to local complements. Finding the optimal graph state (e.g., minimizing edges or maximum degree) within an LC orbit is essential for resource efficiency, but heuristic methods cannot guarantee optimality without a complete characterization of the orbit.

2. Methodology

The authors introduce a novel approach based on Split Decomposition to characterize and count LC orbits, specifically for Distance-Hereditary (DH) graphs.

Split Decomposition: A technique (by Cunningham) that recursively breaks a graph into simpler components (quotient graphs) using "splits" (bipartitions where crossing edges form a complete bipartite subgraph).
Quotient-Augmented Strong Split Tree (QASST): The authors define a new tool, the QASST, which is a graph-labeled tree representing the split decomposition.
- Nodes: Internal nodes are labeled with quotient graphs (which are either complete, star, or prime graphs).
- Leaves: Represent the original vertices of the graph.
- Edges: Represent strong splits.
Key Insight for DH Graphs: Distance-Hereditary graphs are "completely separable," meaning their split decomposition contains only star and complete quotient graphs (no prime graphs).
Propagation of Local Complements: The paper establishes that a local complement on a graph induces a specific sequence of local complements on the quotient graphs within the QASST. This propagation occurs recursively through the tree via pairs of "split-nodes."
QASST Equivalence vs. LC Equivalence:
- The authors define QASST equivalence: Two graphs are QASST equivalent if they share the same strong split tree and their corresponding quotient graphs are locally equivalent.
- Theorem: If two graphs are LC equivalent, they must be QASST equivalent. However, the converse is not always true (QASST equivalence is a necessary but not sufficient condition for LC equivalence).
- Strategy: The authors calculate the size of the QASST equivalence class (an upper bound) and then subtract "invalid" combinations of quotient graphs that do not preserve strong splits. They then prove that for specific DH families, the lower bound (derived via explicit transformations) matches this upper bound, yielding exact orbit sizes.

3. Key Contributions

General Framework: Developed a method to count LC orbit sizes for distance-hereditary graphs by analyzing the symmetry classes of quotient graphs in the QASST.
Explicit Formulas: Derived exact formulas for the size of LC orbits for several broad families of distance-hereditary graphs:
- Complete bipartite graphs ( $K_{n,m}$ ).
- Complete $k$ -partite graphs ( $K_{n_1, \dots, n_k}$ ).
- Clique-stars ( $CS^r_{n_1, \dots, n_k}$ ).
- Multi-leaf repeater graphs ( $MR_{n_1, \dots, n_k}$ ).
Classification of Orbits: Proved that for complete $k$ -partite graphs and clique-stars, the QASST equivalence class is partitioned into exactly two disjoint LC orbits (one for the complete $k$ -partite type and one for the clique-star type), distinguished by the parity of the number of star-spoke quotient graphs.
Optimization Representatives: Identified specific graphs within these orbits that minimize:
- Edge Count: Finding the "sparsest" graph in the orbit.
- Maximum Vertex Degree: Finding the graph with the lowest maximum degree (relevant for circuit depth in quantum computing).
Isomorphism Analysis: Derived formulas for the number of distinct isomorphism classes (unlabeled graphs) within these LC orbits, showing how symmetry reduces the count compared to labeled graphs.

4. Key Results

Complete Bipartite Graphs ( $K_{n,m}$ ):
- Orbit Size: $|O(K_{n,m})| = nm + n + m + 3$ (for $n, m \ge 2$ ).
- Minimal Edge Representative: A "binary star" graph with $n+m-1$ edges.
Complete $k$ -Partite Graphs ( $K_{n_1, \dots, n_k}$ ):
- Orbit Size: A formula involving products of $(n_i + 1)$ with specific parity constraints (even products of $n_i$ ).
- The orbit size depends on whether $k$ is even or odd and the relative sizes of $n_i$ .
Clique-Stars ( $CS^r_{n_1, \dots, n_k}$ ):
- Orbit Size: Similar to $K_{n_1, \dots, n_k}$ but involves odd products of $n_i$ .
- Theorem: $K_{n_1, \dots, n_k}$ and $CS^r_{n_1, \dots, n_k}$ are not locally equivalent, yet they share the same QASST structure. Their orbits are disjoint and together exhaust the QASST equivalence class.
Multi-Leaf Repeater Graphs:
- These are shown to be locally equivalent to $K_{n_1, \dots, n_k}$ if $k$ is even, and to $CS^r_{n_1, \dots, n_k}$ if $k$ is odd.
Minimal Edge/Degree Formulas: The paper provides explicit conditions (based on $k$ and the values of $n_i$ ) to determine which symmetry class yields the graph with the minimum number of edges or minimum maximum degree.

5. Significance

Mathematical Advancement: This work extends Bouchet's foundational results from paths and cycles to complex, highly symmetric graph families. It resolves the enumeration problem for a significant class of graphs where brute-force methods fail.
Quantum Information Impact:
- Resource Optimization: By providing exact formulas for the size of LC orbits and identifying minimal edge/degree representatives, the paper enables the design of more efficient quantum circuits and graph states.
- Error Correction: Distance-hereditary graphs (especially trees and repeaters) are robust against vertex loss (photon loss in optical systems). Characterizing their LC orbits helps in designing fault-tolerant quantum repeater networks.
- Algorithmic Efficiency: The QASST-based approach offers a polynomial-time method (relative to the graph size) to analyze equivalence classes, bypassing the #P-complete nature of the general problem.
Future Directions: The authors suggest extending these techniques to non-distance-hereditary graphs (involving prime quotient graphs) and applying the QASST construction to study vertex minors, a related hard problem in graph theory.

In summary, the paper successfully bridges graph theory and quantum information by using split decomposition to solve the intractable problem of counting local equivalence classes for distance-hereditary graphs, providing both theoretical formulas and practical tools for optimizing quantum graph states.