Premium
The edge reconstruction number of a disconnected graph
Author(s) -
Molina Robert
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190310
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , edge transitive graph , isomorphism (crystallography) , discrete mathematics , complement graph , totally disconnected space , graph power , line graph , locally compact space , chemistry , crystal structure , crystallography
The edge reconstruction number of a graph G, RN(G) , is the minimum number of edge deleted subgraphs required to determine G up to isomorphism. We prove the following results for a disconnected graph G with at least two nontrivial components. If G has a pair of nontrivial nonisomorphic components then RN(G) ≤ 3. If G has a pair of nontrivial nonisomorphic components, is not a forest, and contains a nontrivial component other than K 3 or K 1,3 then RN(G) ≤ 2. Finally, if all nontrivial components of G are isomorphic to a graph with k edges, then RN(G) ≤ k + 2. The edge reconstruction results in this paper are similar to the vertex reconstruction results stated by Myrvold (“The Ally‐Reconstruction Number of a Disconnected Graph,” Ars Combinatoria , Vol. 28 [1989] pp. 123‐127), but a significant difference is that the edge reconstruction number of a disconnected graph is often two, while the vertex reconstruction number of a graph is always three or more. © 1995 John Wiley & Sons, Inc.