Two identities of hook immanantal polynomials of (di)graphs and their applications
Tingzeng Wu, Wenwei Zhang, Hong-Jian Lai · 2025
Read Two identities of hook immanantal polynomials of (di)graphs and their applications by Tingzeng Wu, Wenwei Zhang, Hong-Jian Lai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-14607.txt.
Description
A 2025 arXiv research paper by Tingzeng Wu, Wenwei Zhang, Hong-Jian Lai. Abstract: Given a graph or a digraph, let M be a combinatorial matrix (adjacency matrix and (signless) Laplacian matrix) of the (di)graph. The polynomial \Phi_{k}^{M}(M,x)=\Phi_{(k,1^{n-k})}^{M}(M,x)=d_{(k,1^{n-k})}(xI-M) is called the hook immanantal polynomial of the (di)graph.
Catalog record
| CREATOR | Tingzeng Wu, Wenwei Zhang, Hong-Jian Lai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-14607
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Two identities of hook immanantal polynomials of (di)graphs and their applications Thanks: supported by NSFC (No. 12261071)and NSF of Qinghai Province (No. 2020-ZJ-920). Tingzeng Wu, Wenwei Zhang, Hong-Jian Lai Abstract Abstract: Given a graph or a digraph, let M be a combinatorial matrix (adjacency matrix and (signless) Laplacian matrix) of the (di)graph. The polynomial \Phi_{k}^{M}(M,x)=\Phi_{(k,1^{n-k})}^{M}(M,x)=d_{(k,1^{n-k})}(xI-M) is called the hook immanantal polynomial of the (di)graph. This article establishes two identities: one is between the hook immanantal polynomial of a digraph and its derivatives, and the hook immanantal polynomials of all subgraphs obtained by deleting one arc from the digraph; the other is between the hook immanantal polynomial of a graph and its derivatives, and the hook immanantal polynomial of all subgraphs obtained by deleting one edge and its endpoints from the graph. As applications, we show that the hook immanantal polynomials of combinatorial matrices of digraphs can be reconstructed from the hook immanantal polynomials of combinatorial matrices of their subdigraphs. We also show that the hook immanantal polynomial of adjacency matirx of a graph can be reconstructed from the hook immanantal polynomials of adjacency matrices of subgraphs of the graph. Keywords: Hook immanant; Graph matrix; Ulam-Kelly conjecture; Edge reconstruction; Vertex reconstruction AMS subject classifications: 05C20; 05C31; 05C60; 05E05; 15A15 1 Introduction Let G=(V(G),E(G)) be a simple graph with vertex set V(G)=\{v_{1},v_{2},\ldots,v_{n}\} and edge set E(G)=\{e_{1},e_{2},\ldots,e_{m}\} . The number of vertices and edges of G denoted by |V(G)|=n and |E(G)|=m , respectively. Let e=v_{s}v_{t} be an edge of G , we may obtain a graph on m-1 edges by deleting v_{s}v_{t} from G but leaving the vertices and the remaining eages intact. The resulting graph is denoted by G-v_{s}v_{t} . Similarly, if \{v_{s},v_{t}|v_{s}v_{t}\in E(G)\} are two vertices of G , we may obtain a graph on n-2 vertices by deleting from G the vertices in \{v_{s},v_{t}\} together with all the edges incident with a vertex in \{v_{s},v_{t}\} . The resulting graph is denoted by G-v_{s}-v_{t} . The degree matrix of G is denoted by D(G)=diag(d_{1},d_{2},\ldots,d_{n}) , where d_{i} is the degree of vertex v_{i} in G . The adjacency matrix of G is an n by n matrix, denoted A(G)=(a_{ij}) whose entry a_{ij} is given by a_{ij}=\begin{cases}1,&\text{if $v_{i}$ and $v_{j}$ are adjacent},\\ 0,&\text{otherwise}.\end{cases} Then L(G)=D(G)-A(G) and Q(G)=D(G)+A(G) are the Laplacian and signless Laplacian matrices of graph G , respectively. Let \overrightarrow{G}=(V(\overrightarrow{G}),E(\overrightarrow{G})) be a digraph with no loops or parallel arcs, where the vertex set V(\overrightarrow{G})=\{v_{1},v_{2},\ldots,v_{n}\} and the arc set E(\overrightarrow{G})=\{\overrightarrow{e_{1}},\overrightarrow{e_{2}},\ldots,\overrightarrow{e_{m}}\} . The number of vertices and edges of \overrightarrow{G} denoted by |V(\overrightarrow{G})|=n and |E(\overrightarrow{G})|=m , respectively. If \overrightarrow{e} is an arc of \overrightarrow{G} , we may obtain a graph on m-1 arcs by deleting \overrightarrow{e} from \overrightarrow{G} but leaving the vertices and the remaining arcs intact. The resulting graph is denoted by {\overrightarrow{G}}-{\overrightarrow{e}} . The adjacency matrix of digraph \overrightarrow{G} is denoted A(\overrightarrow{G})=(a_{ij})_{n\times n} , where a_{ij}=\begin{cases}1,&\text{if }(v_{i},v_{j})\in E(\overrightarrow{G}),\\ 0,&\text{otherwise}.\end{cases} The vertex in-degree diagonal matrix of digraph \overrightarrow{G} is denoted D(\overrightarrow{G})=diag(d^{-}(v_{1}),d^{-}(v_{2}),\ldots,\\ d^{-}(v_{n})) , where the d^{-}(v_{i}) is in-degree of vertex v_{i} . Then L(\overrightarrow{G})=D(\overrightarrow{G})-A(\overrightarrow{G}) and Q(\overrightarrow{G})=D(\overrightarrow{G})+A(\overrightarrow{G}) are the Laplacian and signless Laplacian matrices of \overrightarrow{G} , respectively. Let \chi_{\lambda} be an irreducible character of the symmetric group S_{n} , indexed by a partition \lambda of n . For an n by n matrix M=(m_{ij}) , the immanant afforded by \chi_{\lambda} is defined as \displaystyle d_{\lambda}(M)=\sum_{\sigma\in S_{n}}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}m_{i\sigma(i)}. For \lambda=(k,1^{n-k}) , the immanant d_{(k,1^{n-k})}(M) is called hook immanant of M , denoted by d_{k}(M) . In particular, d_{1}(M)={\rm det}M , the determinant of M , and d_{n}(M)={\rm per}M , the permanent of M . Bürgisser [ 1 ] showed that computing the hook immanant of M is VNP-complete. The study of immanants of matrices is well elaborated in [ 3 , 11 , 13 , 18 , 19 , 24 , 30 ] and the references cited therein. Furthermore, the immanants of graph matrices received a lot of attention, as seen in [ 6 , 7 , 20 , 21 , 22 ] , among others. Let I_{n} be an n by n identity matrix. The hook immanantal polynomial \Phi_{k}^{M}(M,x) of an n by n matrix M associated with the character \chi_{(k,1^{n-k})} is the hook immanant d_{(k,1^{n-k})}(xI_{n}-M) , denoted by \displaystyle\Phi_{k}^{M}(M,x)=\Phi_{(k,1^{n-k})}^{M}(M,x)=d_{(k,1^{n-k})}(xI_{n}-M). (1) Bürgisser [ 1 ] showed that computing the hook immanantal polynomial of M is VNP-complete. Merris [ 2 ] stated that almost all trees share a complete set of immanantal polynomials. Cash [ 4 ] generalized the Sachs theorem to immanantal polynomial and applied it to chemical graphs containing hydrocarbon structures. Yu [ 33 ] represented the specific expression of the immanantal polynomial of M using the basic subgraphs. Further study on immanantal polynomial is presented in [ 23 , 27 , 32 ] . By ( 1 ), let M denote the adjacency matrix A(\overrightarrow{G}) (or A(G) ), the Laplacian matrix L(\overrightarrow{G}) (or L(G) ) and the signless Laplacian matrix Q(\overrightarrow{G}) (or Q(G) ) of a digraph \overrightarrow{G} (or a graph G ), then \Phi^{A}_{k}(\overrightarrow{G},x) , \Phi^{L}_{k}(\overrightarrow{G},x) , \Phi^{Q}_{k}(\overrightarrow{G},x) , \Phi^{A}_{k}(G,x) , \Phi^{L}_{k}(G,x) and \Phi^{Q}_{k}(G,x) denote the hook immanantal polynomials of these matrices, respectively, as follow: \begin{split}\begin{aligned} \Phi^{A}_{k}(\overrightarrow{G},x)&=d_{k}(xI_{n}-A(\overrightarrow{G})),~~\\ \Phi^{L}_{k}(\overrightarrow{G},x)&=d_{k}(xI_{n}-L(\overrightarrow{G})),~~\\ \Phi^{Q}_{k}(\overrightarrow{G},x)&=d_{k}(xI_{n}-Q(\overrightarrow{G})),~~\end{aligned}&\begin{aligned} \Phi^{A}_{k}(G,x)&=d_{k}(xI_{n}-A(G)),\\ \Phi^{L}_{k}(G,x)&=d_{k}(xI_{n}-L(G)),\\ \Phi^{Q}_{k}(G,x)&=d_{k}(xI_{n}-Q(G)).\end{aligned}\end{split} (2) In particular, \Phi_{1}^{A}(\overrightarrow{G},x) ( \Phi_{1}^{A}(G,x) , resp.) and \Phi_{n}^{A}(\overrightarrow{G},x) ( \Phi_{n}^{A}(G,x) , resp.) are respectively the characteristic and permanental polynomial of \overrightarrow{G} ( G , resp.). For each function f(x) in ( 2 ), let f^{\prime}(x) denote its derivative. For a digraph \overrightarrow{G} , we will show the following identity ( 3 ) revealing a relationship among the hook immanantal polynomial of \overrightarrow{G} and its derivatives, and the hook immanantal polynomials of all subdigraphs in \{\overrightarrow{G}-\overrightarrow{e}|{\overrightarrow{e}}\in E({\overrightarrow{G}})\} . Theorem 1 . Let \overrightarrow{G} be a digraph with no loops or parallel arcs, which vertex set V(\overrightarrow{G})=\{v_{1},v_{2},\ldots,v_{n}\} and arc set E(\overrightarrow{G})=\{\overrightarrow{e_{1}},\overrightarrow{e_{2}},\ldots,\overrightarrow{e_{m}}\} . For M\in\{A,L,Q\} , let \Phi^{M}_{k}(\overrightarrow{G},x) be defined as in ( 2 ) and \Phi^{\prime M}_{k}(\overrightarrow{G},x) denote its derivative. Then the following holds: \displaystyle(m-n)\Phi^{M}_{k}({\overrightarrow{G}},x)+x\Phi^{\prime M}_{k}({\overrightarrow{G}},x)=\sum_{{\overrightarrow{e}}\in E({\overrightarrow{G}})}\Phi^{M}_{k}({\overrightarrow{G}}-{\overrightarrow{e}},x). (3) For convenience, let {\Phi}^{{A}({\square\!\square})}_{k}(G-v_{s}-v_{t},x)=d_{(k-2,1^{n-k})}(xI_{n-2}-A(G-v_{s}-v_{t})) denote the hook immanantal polynomial of A(G-v_{s}-v_{t}) corresponding to the partition (k-2,1^{n-k}) , which is obtained from the partition (k,1^{n-k}) of d_{k}(xI_{n}-A(G)) by removing a rim hook of the form {\square\!\square} from the Young tableau associated with (k,1^{n-k}) , and let {\Phi}^{{A}{(\scriptsize\rotatebox{90.0}{$\square\!\square$})}}_{k}(G-v_{s}-v_{t},x)=d_{(k,1^{n-k-2})}(xI_{n-2}-A(G-v_{s}-v_{t})) denote the hook immanantal polynomial of A(G-v_{s}-v_{t}) corresponding to the partition (k,1^{n-k-2}) , which is obtained from the partition (k,1^{n-k}) of d_{k}(xI_{n}-A(G)) by removing a rim hook of the form \square\!\square from the Young tableau associated with (k,1^{n-k}) . Similarly to the digraph \overrightarrow{G} , there exists an identity for the hook polynomial of the graph G . Theorem 2 . Let G be a simple graph with vertex set V(G)=\{v_{1},v_{2},\ldots,v_{n}\} and edge set E(G)=\{e_{1},e_{2},\ldots,e_{m}\} . For the graph polynomial \Phi^{A}_{k}(G,x) defined as in ( 2 ) and \Phi^{\prime A}_{k}(G,x) denote its derivative. Then the following holds: \displaystyle(m-n)\Phi^{A}_{k}(G,x)+x\Phi^{\prime A}_{k}(G,x) (4) \displaystyle= \displaystyle\sum_{{v_{s}v_{t}}\in E(G)}[\Phi^{A}_{k}(G-v_{s}v_{t},x)-{\Phi}^{{A}({\square\!\square})}_{k}(G-v_{s}-v_{t},x)+{\Phi}^{{A}{(\scriptsize\rotatebox{90.0}{$\square\!\square$})}}_{k}(G-v_{s}-v_{t},x)]. The famous Ulam-Kelly’s vertex reconstruction conjecture [ 31 ] stated that each simple graph G with at least three vertices can be uniquely reconstructed from its set of vertex induced subgraphs \{G-v|v\in V(G)\} . Harary [ 14 , 15 ] proposed a similar conjecture, called edge reconstruction conjecture, which asserts that every simple graph G with edge set E(G) can be reconstructed from its set of edge subgraphs \{G-e|e\in E(G)\} if