Reconstructing edge-deleted unicyclic graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929577231646720 |
|---|---|
| author | Pizzimenti, Anthony E. Rakhimov, Umarkhon |
| author_facet | Pizzimenti, Anthony E. Rakhimov, Umarkhon |
| contents | The Harary reconstruction conjecture states that any graph with more than four edges can be uniquely reconstructed from its set of maximal edge-deleted subgraphs. In 1977, Müller verified the conjecture for graphs with $n$ vertices and $n \log_2(n)$ edges, improving on Lovás's bound of $\log(n^2-n)/4$. Here, we show that the reconstruction conjecture holds for graphs which have exactly one cycle and and three non-isomorphic subtrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03133 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconstructing edge-deleted unicyclic graphs Pizzimenti, Anthony E. Rakhimov, Umarkhon Combinatorics Data Structures and Algorithms The Harary reconstruction conjecture states that any graph with more than four edges can be uniquely reconstructed from its set of maximal edge-deleted subgraphs. In 1977, Müller verified the conjecture for graphs with $n$ vertices and $n \log_2(n)$ edges, improving on Lovás's bound of $\log(n^2-n)/4$. Here, we show that the reconstruction conjecture holds for graphs which have exactly one cycle and and three non-isomorphic subtrees. |
| title | Reconstructing edge-deleted unicyclic graphs |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.03133 |