On the fixed edge of planar graphs with minimum degree five
type: Item
instance of: scholarly article
title: On the fixed edge of planar graphs with minimum degree five
zbMATH Open document ID: 0858.05078
DOI: 10.1016/0012-365X(94)00280-V
published in: Discrete Mathematics
publication date: 1997-03-23T00:00:00Z
review text: An edge \(e\) of a finite simple graph \(G\) is called a fixed edge of \(G\) if \(G-e+e'\approx G\) implies \(e=e'\). The topic of fixed edges is interesting in its own right, and of particular interest to those working in graph reconstruction since certain classes of graphs can be shown to be edge reconstructible using fixed edge arguments. The main result of this paper is that a planar graph with minimum degree 5 must contain a fixed edge. The proof is quite short, but uses a result of Lauri (\textit{J. Lauri} [Edge-reconstruction of planar graphs with minimum degree 5, J. Graph Theory 3, 269-286 (1979; Zbl 0438.05048)]) about 2-connected planar graphs of minimum degree 5. The authors use their fixed edge theorem to show that planar graphs satisfying certain degree requirements are edge reconstructible. If \(G\) is a connected graph with minimum degree 1, then the trunk of \(G\), denoted \(G^\#\), is defined to be the maximal subgraph of \(G\) with minimum degree \(\geq2\). The reconstruction result in this paper states that if \(G\) is a planar graph of minimum degree 1, and if \(G^\#\) has minimum degree 5, then \(G\) is edge reconstructible. This result is a direct corollary of the main theorem on fixed edges.
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 897591
zbMATH Keywords: fixed edge
zbMATH Keywords: graph reconstruction
zbMATH Keywords: planar graph
zbMATH Keywords: edge reconstructible
zbMATH Keywords: trunk
author: Baogang Xu
author: Hongbing Fan
reviewed by: Robert R. Molina
MaRDI profile type: MaRDI publication profile
cites work: The reconstruction for separable graphs with 2-connected trunks that are series-parallel networks
cites work: Q5422499
cites work: Q5544087
cites work: Edge‐reconstruction of planar graphs with minimum valency 5
cites work: Fixing subgraphs and Ulam's conjecture
cites work: Fixing subgraphs
Recommended article: Q4287199
Recommended article: Q4289747
Recommended article: Q4321819
Recommended article: Q4308485
Recommended article: Q4306325
Recommended article: Q3816103
Recommended article: On the edge-reconstruction of 3-connected planar graphs with minimum valency 4
Recommended article: Edge-reconstruction of minimally 3-connected planar graphs
Recommended article: Q4388580
Recommended article: Paths with restricted degrees of their vertices in planar graphs
description: scientific article; zbMATH DE number 897591