Reconstructing graphs from their k-edge deleted subgraphs
type: Item
instance of: scholarly article
title: Reconstructing graphs from their k-edge deleted subgraphs
zbMATH Open document ID: 0595.05050
DOI: 10.1016/0095-8956(87)90013-X
published in: Journal of Combinatorial Theory. Series B
publication date: 1987-01-01T00:00:00Z
review text: Let G be a graph with m edges and n vertices. We show that if \(2^{m- k}>n!\) or if \(2m>\left( \begin{matrix} n\\ 2\end{matrix} \right)+k\) then G is determined by its collection of k-edge deleted subgraphs.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 3957158
zbMATH Keywords: graph reconstruction
zbMATH Keywords: k-edge deleted subgraphs
author: Chris Godsil
author: Ilia Krasikov
author: Yehuda Roditty
MaRDI profile type: Publication
cites work: Graph reconstruction—a survey
cites work: On the number of sets in a null t-design
cites work: On the Structure oft-Designs
cites work: Q5544087
cites work: Balance equations for reconstruction problems
cites work: A note on the line reconstruction problem
cites work: The edge reconstruction hypothesis is true for graphs with more than n log n edges
cites work: Quotients of Peck posets
cites work: Reconstruction from vertex-switching
full work available at URL: 0095-8956(87)90013-x
OpenAlex ID: W2167155956
description: scientific article; zbMATH DE number 3957158