2015/03/03 by Michael S. Ross, Ross, Michael S.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1503.01048
arxiv created 2015/03/03 · openalex publication_date 2015/03/03 · arxiv updated 2015/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The edge-reconstruction number of graph G, denoted ern(G),is the size of the smallest multiset of edge-deleted, unlabeled subgraphs of G, from which the structure of G can be uniquely determined. That there was some connection between the areas of edge reconstruction and swappability has been known since the swapping number of a graph was first introduced by Froncek, Rosenberg, and Hlavacek in 2013. This paper illustrates the depth of that connection by proving several bridging results between those areas; in particular, when the graphs in question are both regular and 2-swappable. These connections led to the discovery of four infinite families of r≥ 3 regular graphs with ern(G) ≥ 3, contradicting the formerly conjectured upper bound.