Metraipolis › archive › dc_2a4be3f4426d
The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two — arXiv:2609.02389
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.02389
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T05:33:01.042Z
- SHA-256 of the archived text
81d30334a868a5f56b8324425e52ea8ac45d8bafcab236919810811cfb6b8eb4- Stable URL of this page
https://metraipolis.com/documento/dc_2a4be3f4426d
How to cite
The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two — arXiv:2609.02389 — arXiv (en), https://arxiv.org/abs/2609.02389 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2a4be3f4426d (Metraipolis archive dc_2a4be3f4426d, sha256 81d30334a868a5f56b8324425e52ea8ac45d8bafcab236919810811cfb6b8eb4)
BibTeX
@misc{dc2a4be3f4426d,
title = {The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two — arXiv:2609.02389},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.02389},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2a4be3f4426d; sha256 81d30334a868a5f56b8324425e52ea8ac45d8bafcab236919810811cfb6b8eb4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02389. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An edge card of a graph is obtained by deleting one edge, and a class edge-reconstruction number asks for the fewest carefully selected cards that identify the graph when its class is known. We determine the sharp universal bound for maximal planar graphs. Two selected cards always suffice, and the octahedral graph shows that two can be necessary; some maximal planar graphs are already identified by one card. The argument exploits the fact that deleting a flippable edge leaves a single quadrilateral whose two diagonals give the only possible maximal-planar completions. Degree information then rules out the competing completion, with a separate argument for graphs containing a vertex of degree three. This settles a problem posed in a 2010 survey on reconstruction numbers. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in math.CO). Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM). Pagina del lavoro: https://arxiv.org/abs/2609.02389 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T04:59:51.781Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).