Browsing by Subject "swapping number"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    2-Swappability and the Edge-Reconstruction Number of Regular Graphs
    (2018-05) Ross, Michael
    The edge-reconstruction number of a graph $G$, denoted $\ERN(G)$, is the size of the smallest multiset of unlabeled, edge-deleted 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 swapping numbers has been known since the swapping number of a graph was first introduced by Froncek, Hlavacek, and Rosenberg in 2014\cite{edgeswap}. The present 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. Formerly, it had been conjectured that for $r\geq 3$ regular graphs, $\ERN(G) \leq 2.$ However, results of the present paper led to the discovery of four infinite families of $r\geq 3$ regular graphs with $\ERN(G) \geq 3$, while giving some promising leads for further discoveries in edge reconstruction.