Generalization and Power of Kocay's Lemma in Graph Reconstruction

2025/08/29 by Philip B. Stark, Stark, Peter
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Theory and Algorithms #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2509.02604

openalex publication_date 2025/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper generalizes Kocay's lemma, with particular applications to graph reconstruction, as well as discussing and proving aspects around the power of these generalizations and Kocay's original lemma, with a result on the reconstruction of the multiplicity of a tree T as a subgraph of G.

Citations

• Subgraph posets and graph reconstruction

Related

• An algebraic formulation of the graph reconstruction conjecture
• The Reconstruction of Graphs
• Reconstructing edge-deleted unicyclic graphs
• A refinement of Kelly's lemma for graph reconstruction for counting rooted subgraphs
• Reconstructibility of the K_r-count from n-1 cards