Reconstruction of a graph of order \(p\) from its \((p-1)\)-complements
type: Item
instance of: scholarly article
title: Reconstruction of a graph of order \(p\) from its \((p-1)\)-complements
zbMATH Open document ID: 0858.05079
author: E. Sampathkumar
author: L. Pushpalatha
published in: Indian Journal of Pure \& Applied Mathematics
publication date: 1996-07-15T00:00:00Z
review text: Let \(G=(V,E)\) be a graph of order \(p\geq 2\) and let \(P=\{V_1,\dots,V_{p-1}\}\) be a partition of \(V\) of order \(p-1\), i.e., the \(V_i\) are disjoint subsets of \(V\) such that \(|V_i|=2\) for exactly one \(V_i\) and \(|V_j|= 1\) for all \(j\neq i\). Then the \((p-1)\)-complement of \(G\) with respect to \(P\) is defined as follows: For all \(V_k\) and \(V_j\) in \(P\), \(k\neq j\), remove the edges between \(V_k\) and \(V_j\), and add the missing edges between them. The authors conjecture that all graphs are reconstructible from the collection of all its \((p-1)\)-complements and verify the correctness of this conjecture for all disconnected, all unicyclic, and all bipartite graphs.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 903322
zbMATH Keywords: reconstruction
reviewed by: Thomas Andreae
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 903322