2-Swappability and the Edge-Reconstruction Number of Regular Graphs
2018-05
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
2-Swappability and the Edge-Reconstruction Number of Regular Graphs
Authors
Published Date
2018-05
Publisher
Type
Thesis or Dissertation
Abstract
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.
Description
University of Minnesota M.S. thesis.May 2018. Major: Applied and Computational Mathematics. Advisor: Dalibor Froncek. 1 computer file (PDF); iv, 16 pages.
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Ross, Michael. (2018). 2-Swappability and the Edge-Reconstruction Number of Regular Graphs. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/200163.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.