Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914356499841024 |
|---|---|
| author | Connolly, Nicholas Nishio, Shin Nemoto, Kae |
| author_facet | Connolly, Nicholas Nishio, Shin Nemoto, Kae |
| contents | Local complement is a graph operation formalized by Bouchet which replaces the neighborhood of a chosen vertex with its edge-complement. This operation induces an equivalence relation on graphs; determining the size of the resulting equivalence classes is a challenging problem in general. Bouchet obtained formulas only for paths and cycles, and brute-force methods are limited to very small graphs. In this work, we extend these results by deriving explicit formulas for several broad families of distance-hereditary graphs, including complete multipartite graphs, clique-stars, and repeater graphs. Our approach uses a technique known as split decomposition to establish upper bounds on equivalence class sizes, and we prove these bounds are tight through a combinatorial enumeration of the graphs' decomposed structure up to symmetry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23825 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions Connolly, Nicholas Nishio, Shin Nemoto, Kae Combinatorics Discrete Mathematics Quantum Physics 05C76(Primary) 05C30, 05C83, 05C90 (Secondary) G.2.1; G.2.2; F.2.1 Local complement is a graph operation formalized by Bouchet which replaces the neighborhood of a chosen vertex with its edge-complement. This operation induces an equivalence relation on graphs; determining the size of the resulting equivalence classes is a challenging problem in general. Bouchet obtained formulas only for paths and cycles, and brute-force methods are limited to very small graphs. In this work, we extend these results by deriving explicit formulas for several broad families of distance-hereditary graphs, including complete multipartite graphs, clique-stars, and repeater graphs. Our approach uses a technique known as split decomposition to establish upper bounds on equivalence class sizes, and we prove these bounds are tight through a combinatorial enumeration of the graphs' decomposed structure up to symmetry. |
| title | Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions |
| topic | Combinatorics Discrete Mathematics Quantum Physics 05C76(Primary) 05C30, 05C83, 05C90 (Secondary) G.2.1; G.2.2; F.2.1 |
| url | https://arxiv.org/abs/2602.23825 |