The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.02389
curl -X POST /api/v1/records/arxiv/2609.02389/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02389/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'