The graph reconstruction number

The reconstruction number of graph G is the minimum number of point-deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. the most striking statement is our concluding conjeture that almost all graphs have have reconstruction number three.     

The class reconstruction number of maximal planar graphs

The reconstruction numberrn(G) of a graphG was introduced by Harary and Plantholt as the smallest number of vertex-deleted subgraphsG _i =G – v _i in the deck ofG which do not all appear in the deck of any other graph. For any graph theoretic propertyP, Harary defined theP-reconstruction number of a graph G P as the smallest number of theG _i in the deck ofG, which do not all appear in the deck of any other graph inP We now study the maximal planar graph reconstruction numberrn(G), proving that its value is either 1 or 2 and characterizing those with value 1.     

The edge reconstruction number of a disconnected graph

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₃ 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.     

Degree-associated reconstruction number of graphs

A card of a graph G is a subgraph formed by deleting one vertex. The Reconstruction Conjecture states that each graph with at least three vertices is determined by its multiset of cards. A dacard specifies the degree of the deleted vertex along with the card. The degree-associated reconstruction number drn(G) is the minimum number of dacards that determine G. We show that drn(G)=2 for almost all graphs and determine when drn(G)=1. For k-regular n-vertex graphs, drn(G)≤min{k+2,n−k+1}. For vertex-transitive graphs (not complete or edgeless), we show that drn(G)≥3, give a sufficient condition for equality, and construct examples with large drn. Our most difficult result is that drn(G)=2 for all caterpillars except stars and one 6-vertex example. We conjecture that drn(G)≤2 for all but finitely many trees.     

The reconstruction theorem for endomorphisms

The reconstruction theorem deals with dynamical systems which are given by a map ψ : M → M together with a read out function 𝒻 : M → ℝ. Restricting to the cases where ψ is a diffeomorphism, it states that for generic (ψ, 𝒻 ) there is a bijection between elements x ∈ M and corresponding sequences (𝒻(x), 𝒻 (ψ(x)), . . . , 𝒻 (ψ ^{k -1}(x))) of k successive observations, at least for k sufficiently big. This statement turns out to be wrong in cases where ψ is an endomorphism. In the present paper we derive a version of this theorem for endomorphisms (and which is equivalent to the original theorem in the case of diffeomorphisms). It justifies, also for dynamical systems given by endomorphisms, the algorithms for estimating dimensions and entropies of attractors from obervations. Received: 20 June 2002     

On the reconstruction of linear codes

For a linear code over GF(q) we consider two kinds of “subcodes” called residuals and punctures. When does the collection of residuals or punctures determine the isomorphism class of the code? We call such a code residually or puncture reconstructible. We investigate these notions of reconstruction and show that, for instance, selfdual binary codes are puncture and residually reconstructible. A result akin to the edge reconstruction of graphs with sufficiently many edges shows that a code whose dimension is small in relation to its length is puncture reconstructible. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 285–291, 1998     

The reconstruction conjecture for finite simple graphs and associated directed graphs

In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let Γ and ${\mathrm{\Gamma }}^{\prime }$ be finite simple graphs with at least three vertices such that there exists a bijective map $f:V(\mathrm{\Gamma })\to V({\mathrm{\Gamma }}^{\prime })$ and for any $v\in V(\mathrm{\Gamma })$, there exists an isomorphism ${?}_v:\mathrm{\Gamma }?v\to {\mathrm{\Gamma }}^{\prime }?f(v)$. Then we define the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}=\stackrel{?}{\mathrm{\Gamma }}(\mathrm{\Gamma },{\mathrm{\Gamma }}^{\prime },f,{\{{?}_v\}}_{v\in V(\mathrm{\Gamma })})$ with two kinds of arrows from the graphs Γ and ${\mathrm{\Gamma }}^{\prime }$, the bijective map f and the isomorphisms ${\{{?}_v\}}_{v\in V(\mathrm{\Gamma })}$. By investigating the associated directed graph $\stackrel{?}{\mathrm{\Gamma }}$, we study when are the two graphs Γ and ${\mathrm{\Gamma }}^{\prime }$ isomorphic.     

The edge-subgraph poset of a graph and the edge reconstruction conjecture

We consider only finite simple graphs in this paper. Earlier we showed that many invariants of a graph can be computed from the isomorphism class of its partially ordered set of distinct unlabeled non-empty induced subgraphs, that is, the subgraphs themselves are not required. In this paper, we consider an analogous problem of reconstructing an arbitrary graph up to isomorphism from its abstract edge-subgraph poset , which we call the -reconstruction problem. We present an infinite family of graphs that are not -reconstructible and show that the edge reconstruction conjecture is true if and only if the graphs in the family are the only graphs that are not -reconstructible. Let be the set of all unlabeled graphs. Let denote the number of homomorphisms from to . Let be a bijection such that for all , we have . We conjecture that is the identity map. Our conjecture is motivated by the homomorphism cancellation results of Lovász. We prove that the conjecture stated above is weaker than the edge reconstruction conjecture.     

带尖角的障碍声波散射区域的反演

对带尖角的障碍声波散射区域进行了反演,其前提条件是整体场满足奇次Dirichlet边界条件．在用Nystrom方法解正问题的过程中,由于采用等距网格积分给尖角处带来很差的收敛性,这是因为双层位势的积分算子的核在尖角处有Mellin型奇性,不再是紧算子;为此采用梯度网格,数值例子表明该处理方法的有效可靠性．     

A note on the reconstruction of sets of finite measure

We prove a measure-theoretic version of a result due to Radcliffe and Scott [8] from 1999 about the reconstruction of infinite sets of real numbers. This answers their question from [8]. This revised version was published online in June 2006 with corrections to the Cover Date.     

An Iterative Algorithm for Angle-limited Three-dimensional Image Reconstruction

We establish an improved GP iterative algorithm for the extrapolation of band-limited function to fully 3-dimensional image reconstruction by the convolution-backprojection algorithm. Numerical experiments demonstrate that the image resolving power of IGP algorithm is better than that of the original GP algorithm for noisy data.     

The polynomial reconstruction problem: The first 50 years

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetkovi? in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations.     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

Dynamics reconstruction using orthonormal functions

A methodology to reconstruct the dynamics associated with a given signal is presented. The methodology is based on the expansion of the function characterizing the dynamical system in terms of orthonormal functions calculated by means of a QR decomposition of the generating functions matrix.     

Shotgun reconstruction in the hypercube

Mossel and Ross raised the question of when a random coloring of a graph can be reconstructed from local information, namely, the colorings (with multiplicity) of balls of given radius. In this article, we are concerned with random 2-colorings of the vertices of the -dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter are required to reconstruct. However, the situation for random colorings is dramatically different: we show that almost every 2-coloring can be reconstructed from the multiset of colorings of balls of radius 2. Furthermore, we show that for , almost every -coloring can be reconstructed from the multiset of colorings of 1-balls.