On the edge reconstruction of six digraph polynomials

Abstract

Let $G=(V,E)$ be a digraph having no loops and no multiple arcs, with vertex set $V=\{v_1,v_2,\dots ,v_n\}$ and arc set $E=\{e_1,e_2,\dots ,e_m\}$. Denote the adjacency matrix and the vertex in-degree diagonal matrix of $G$ by $A=(a_{ij}{)}_{n\times n}$ and $D=diag(d^{+}(v_1),d^{+}(v_2),\cdots ,d^{+}(v_n))$, where $a_{ij}=1$ if $(v_i,v_j)\in E(G)$ and $a_{ij}=0$ otherwise, and $d^{+}(v_i)$ is the number of arcs with head $v_i$. Set $f_1(G;x)=\det (xI-A),f_2(G;x)=\det (xI-D+A),f_3(G;x)=\det (xI-D-A),f_4(G;x)=\mathrm{per}(xI-A),f_5(G;x)=\mathrm{per}(xI-D+A),f_6(G;x)=\mathrm{per}(xI-D-A)$, where $\det (X)$ and $\mathrm{per}(X)$ denote the determinant and the permanent of a square matrix $X$, respectively. In this paper, we consider a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, and prove that, for any $1\le i\le 6$, \begin{equation*} (m-n)f_i(G;x)+xf_i'(G;x)=\sum\limits_{e\in E}f_i(G-e;x), \end{equation*} which implies that if $m\ne n$, then $f_i(G;x)$ can be reconstructed from $\{f_i(G-e;x)|e\in E\}$.