On the edge reconstruction of six digraph polynomials

MaRDI QIDQ6436477zbMATH OpenFDO

Authors Jingyuan Zhang, Xianan Jin, Weigen Yan

Publication date 13 May 2023

Abstract: Let $G=(V,E)$ be a digraph having no loops and no multiple arcs, with vertex set $V=v_1,v_2,ldots,v_n$ and arc set $E=e_1,e_2,ldots,e_m$. Denote the adjacency matrix and the vertex in-degree diagonal matrix of $G$ by $A=(a_{ij}{)}_{nimesn}$ and $D=diag(d^{+}(v_1),d^{+}(v_2),cdots,d^{+}(v_n))$, where $a_{ij}=1$ if $(v_i,v_j)inE(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)=mper(xI-A),f_5(G;x)=mper(xI-D+A),f_6(G;x)=mper(xI-D-A)$, where $det(X)$ and $mper(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 $1leqileq6$, �egin{equation*} (m-n)f_i(G;x)+xf_i'(G;x)=sumlimits_{ein E}f_i(G-e;x), end{equation*} which implies that if $meqn$, then $f_i(G;x)$ can be reconstructed from $f_i(G-e;x)|einE$.

This page was built for publication: On the edge reconstruction of six digraph polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436477)