Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions

• URL: http://arxiv.org/abs/2602.23825v1
• Date: Fri, 27 Feb 2026 09:07:41 GMT
• Title: Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions
• Abstract summary: Local complement is a graph operation which replaces the neighborhood of a chosen edge-complement with its edge-complement.<n> determining the size of the resulting equivalence classes is a challenging problem in general.<n>We extend these results by deriving explicit formulas for several broad families of distance-hereditary graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Cycle-Structure Generating Functions for Special Breakpoint Graphs [0.0]
  Breakpoint graphs originate in comparative genomics, where their alternating cycles encode relationships between genomes.<n>We study a constrained class of three-colored breakpoint graphs associated with permutations and develop cycle-refined generating functions for two extremal families.<n>The results determine the leading and constant-order moments entering the Rényi entropy expansion, with the projective-plane contribution giving the finite-size constant correction.
  arXiv  Detail & Related papers  (2026-08-31T13:29:37Z)
• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design.<n>We propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs.<n>We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy.
  arXiv  Detail & Related papers  (2026-07-08T10:15:17Z)
• Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology [0.0]
  We present the Chromatic Persistence Algorithm (CPA), an event-driven method for computing persistent cohomological features of weighted graphs via graphic arrangements.<n>We establish rigorous results: CPA is exponential in the worst case, fixed- parameter tractable in treewidth, and nearly linear for common graph families such as trees, cycles, and series-parallel graphs.
  arXiv  Detail & Related papers  (2025-12-23T12:29:58Z)
• HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity [48.62389920549271]
  HeNCler learns a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition.<n>Our approach enables spectral clustering on an asymmetric similarity graph, providing flexibility for both directed and undirected graphs.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Hyperbolic Heterogeneous Graph Attention Networks [3.0165549581582454]
  Most previous heterogeneous graph embedding models represent elements in a heterogeneous graph as vector representations in a low-dimensional Euclidean space. We propose Hyperbolic Heterogeneous Graph Attention Networks (HHGAT) that learn vector representations in hyperbolic spaces with meta-path instances. We conducted experiments on three real-world heterogeneous graph datasets, demonstrating that HHGAT outperforms state-of-the-art heterogeneous graph embedding models in node classification and clustering tasks.
  arXiv  Detail & Related papers  (2024-04-15T04:45:49Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  We study the so-called emph$k$-core estimator, which outputs a correspondence that induces a large, common subgraph of both graphs. We specialize our general framework to derive new results on exact and partial recovery in correlated block models, correlated Chung-Lu geometric graphs, and correlated random graphs.
  arXiv  Detail & Related papers  (2023-02-10T18:21:35Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  This paper proposes a novel self-supervised learning method, termed as Geometry Contrastive Learning (GCL) GCL views a heterogeneous graph from Euclidean and hyperbolic perspective simultaneously, aiming to make a strong merger of the ability of modeling rich semantics and complex structures. Extensive experiments on four benchmarks data sets show that the proposed approach outperforms the strong baselines.
  arXiv  Detail & Related papers  (2022-06-25T03:54:53Z)
• Heterogeneous manifolds for curvature-aware graph embedding [6.3351090376024155]
  Graph embeddings are used in a broad range of Graph ML applications. The quality of such embeddings crucially depends on whether the geometry of the space matches that of the graph.
  arXiv  Detail & Related papers  (2022-02-02T18:18:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.