Reconstructing the Characteristic (Permanental) Polynomial of a Digraph from Similar Polynomials of its Arc-deleted Subgraphs

Vladimir R. Rosenfeld

Kragujevac Journal of Mathematics, Tome 49 (2025) no. 5, p. 741

Résumé

Let $D=D(V, E)$ be an arbitrary digraph with the set $V$ of vertices and the set $E$ of arcs $\left(|V|=n; |E|=m\right)$; loops, if any, are considered reduced arcs with the same head and tail. The {\em characteristic polynomial $\phi^{-}(D;x)$ $($resp. permanental polynomial $(\phi^{+}))$ of $D$} is the characteristic (permanental) polynomial of its adjacency matrix $A$: $\phi(D;x){:=}\det(xI-A)$ $\left(\phi^{+}(D;x){:=}\mathrm{per}(xI+A)\right)$, where $I$ is an identity matrix. A $t$-arcs-deleted subgraph $D_{t}$ of $D$ is the digraph $D$ less exactly $t$ arcs (while all $n$ vertices are preserved). Also, let $\mathcal{D}_{t}$ and $R_{t}^{-}(D;x)$ $\left(R_{t}^{+}(D;x)\right)$ be the collection (multiset) of all ext{$t$-arc-deleted} subgraphs of $D$ and the sum of the characteristic (permanental) polynomials of all subgraphs from $\mathcal{D}_{t}$, respectively. We consider the reconstruction of the characteristic polynomial $\phi^{-}(D;x)$ (permanental polynomial $\phi^{+}(D;x)$) of $D$ from the polynomial sum $R_{t}^{-}(D;x)$ $\left(R_{t}^{+}(D;x)\right)$, $t\in\{1, 2, \ldots, m-n+n_{0}\}$, where $n_{0}$ is the number of zero roots of $\phi^{-}(D;x)$ $\left(\phi^{+}(D;x)\right)$. Then, we also carry over our reasoning to the case of reconstructing both polynomials of undirected graphs (where edges are deleted).

Détail

Classification : 15A18, 05C50, 05C20
Keywords: characteristic polynomial, permanental polynomial, t-arcs-deleted subgraph.