Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 1 h ago
PreprintCC BY 4.0arXiv

The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two

  • Sergey Ivanov
Open at sourcePDFDOICite

Abstract

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.

Related

  1. A planar signed graph with circular chromatic number five
    Lujia Wang, Huan Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Total eight-colorings of maximal planar graphs of maximum degree six
    Enqiang Zhu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Spreads of degrees in maximal planar graphs -- an exposition
    Yair Caro, Riste Škrekovski, Christina Zarb
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The_Quadratic_Conjecture_and_p-groups_of_maximal_class
    Jingjing Duan, Lijian An
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. Critical molecular theory and the maximal admissible class for Goldberg-type splittings of hp(ℝn), 0<p≤ 1
    Mohamed El Aoumari
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ivanov2026class,
  title = {{The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two}},
  author = {Sergey Ivanov},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02389},
  eprint = {2609.02389},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02389},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two
AU  - Sergey Ivanov
PY  - 2026
DA  - 2026/09/02
PB  - arXiv
DO  - 10.48550/arxiv.2609.02389
UR  - https://arxiv.org/abs/2609.02389
AB  - 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.
ER  -