On the weak reconstruction of Cartesian-product graphs
type: Item
instance of: scholarly article
title: On the weak reconstruction of Cartesian-product graphs
zbMATH Open document ID: 0858.05076
DOI: 10.1016/0012-365X(95)00185-Y
author: Wilfried Imrich
author: Janez Žerovnik
published in: Discrete Mathematics
publication date: 1997-03-23T00:00:00Z
review text: The authors prove the startling result that a non-trivial connected Cartesian-product graph (finite or infinite) can be reconstructed from a single vertex-deleted subgraph. While the membership recognition problem is addressed through the algorithm developed in [\textit{J. Feigenbaum}, \textit{J. Herschberger} and \textit{A. A. Schäffer}, A polynomial time algorithm for finding the prime factors of Cartesian-product graphs, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028)], the weak reconstruction problem is settled here by proving the following: If \(H\) is an arbitrary finite or infinite connected graph and if \(G_1=H\cup x\cup E_x\) and \(G_2=H\cup y\cup E_y\) are one vertex extensions of \(H\), where \(E_x=\{\{x,z\}\mid \{x,z\}\in E(G_1)\}\) and \(E_y=\{\{y,z\}\mid \{y,z\}\in E(G_2)\}\), then \(G_1\) and \(G_2\) are isomorphic, provided they are Cartesian-product graphs.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 895997
zbMATH Keywords: prime factor
zbMATH Keywords: convex subgraph
zbMATH Keywords: product square
zbMATH Keywords: Cartesian-product graph
zbMATH Keywords: membership recognition problem
zbMATH Keywords: reconstruction
MaRDI profile type: Publication
cites work: Cartesian graph factorization at logarithmic cost per edge
cites work: Q4063492
cites work: A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
cites work: On Factorable Extensions and Subgraphs of Prime Graphs
cites work: Q4294601
cites work: Graph multiplication
cites work: Q3259049
full work available at URL: 0012-365x(95)00185-y
OpenAlex ID: W2038224452
description: scientific article; zbMATH DE number 895997