2013/12/04 by Kevin J. Asciak, Asciak, Kevin, Josef Lauri +5
Computer Science · Mathematics · #05C05 #05C60 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1312.1234
openalex publication_date 2013/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The edge-reconstruction number ern(G) of a graph G is equal to the minimum number of edge-deleted subgraphs G-e of G which are sufficient to determine G up to isomorphsim. Building upon the work of Molina and using results from computer searches by Rivshin and more recent ones which we carried out, we show that, apart from three known exceptions, all bicentroidal trees have edge-reconstruction number equal to 2. We also exhibit the known trees having edge-reconstruction number equal to 3 and we conjecture that the three infinite families of unicentroidal trees which we have found to have edge-reconstruction number equal to 3 are the only ones.