# Algebraic Formulation of Graph Reconstruction [closed]

Background

Let $$G$$ be a finite graph on $$v$$ vertices. The deck, $$D(G)$$, of $$G$$ is the multi-set of vertex-deleted subgraphs of $$G$$. The Graph Reconstruction Conjecture asserts that for finite graphs $$G$$ and $$H$$ on $$v\ge 3$$ vertices, if $$D(G)=D(H)$$, then $$G\cong H$$.

Motivation

Consider a graph $$G$$ and chose a vertex labeling $$\phi:[v]\to V(G)$$ where $$[v]=\{1,\dots,v\}$$ and $$V(G)$$ is the vertex set of $$G$$. We denote the $$i$$-th vertex-deleted subgraph of $$G$$ by $$G_i$$ which corresponds to deleting the $$i$$-th vertex and all incident edges and $$D(G)=\{G_1,\dots, G_v\}$$.

For each $$G_i$$, chose a map $$\psi_i:[v]\setminus\{i\}\to V(G_i)$$. From this vertex labeling we may construct an adjacency matrix in which the $$(r,c)$$-th entry of the matrix is $$1$$ if edge $$\{r,c\}$$ is present and $$0$$ otherwise. The dimension of this matrix is $$(v-1)\times (v-1)$$. We can extend this matrix to a $$v\times v$$ matrix by inserting a zero row and column in the $$i$$-th row/column and we will denote this matrix by $$A_i$$. The interpretation of this matrix is that it is the adjacency matrix for $$G_i$$ with a disjoint point appended to the graph.

We now introduce the following theorem:

Theorem Consider the set of adjacency matrices for the vertex-deleted subgraphs of a graph $$G$$ (where the vertex labeling is fixed) and the matrices are extended by a point as explained above. Denote each matrix as $$A_i$$. Then,

$$\frac{1}{v-2}\displaystyle\sum_{i=1}^{v} A_i = A$$

where $$A$$ is the adjacency matrix of $$G$$.

Consider a function $$\Gamma:Sym(v)^v \to \mathbb{R}^{v\times v}$$ where $$Sym(v)$$ is the group of $$v\times v$$ permutations matrices. The function has the following form:

$$\Gamma_D(S)= \frac{1}{v-2} \displaystyle\sum_{i=1}^{v} S_i A_i S_i^T$$

where $$S=(S_1,\dots,S_v)\in Sym(v)^v$$ and $$D$$ denotes the sum is taken over adjacency matrix constructed via the method describe above from deck $$D$$.

For arbitrary choice of $$\psi_i$$ and $$S$$, it is not necessarily the case that $$\Gamma_D(S)$$ is an adjacency matrix (i.e. binary, symmetric, trace of zero). However, if it is, it seems that $$\psi_i$$ permuted by $$S_i$$ would define a coherent reconstruction of the graph.

Conclusion

Overall, the aim of this function $$\Gamma$$ is to provide an algebraic framework for graph reconstruction. In other words, it seems that if $$\Gamma_D(S)$$ and $$\Gamma_D(R)$$ are adjacency matrix and $$\Gamma_D(S) = \Gamma_D(R)$$ then $$R$$ is necessarily a permutation of $$S$$, hence the underlying reconstructed graphs are isomorphic.

Note

I apologize for the length on strange formulation of these ideas. The process is a bit difficult to describe. Please feel free to comment with suggestions and questions to improve clarity.

• What is the question? Commented Feb 5, 2021 at 1:33