Immanantal polynomials of the linear combination matrices of graphs Thanks: *Corresponding author Xiangshuai Dong, Tingzeng Wu ∗ Abstract . The immanant is a generalized matrix function associated with irreducible characters of the symmetric group. The immanantal polynomial of matrix M M is defined as the immanant of matrix ( x ​ I − M ) (xI-M) , where I I is the identity matrix. The characteristic polynomials and permanental polynomials of graph matrices (adjacency matrix, Laplacian matrix, signless Laplacian matrix and A α ​ ( G ) A_{\alpha}(G) matrix) have been extensively studied, yielding fascinating results. As a unification of the characteristic polynomial and permanental polynomial, the immanantal polynomial has also attracted attention and led to several important findings. In this paper, we focus on the study of immanantal polynomials for linear combination matrices composed of the degree matrix and adjacency matrix of a graph. First, applying the concept of vertex orientation for general graphs, we provide a combinatorial interpretation of the coefficients of the immanantal polynomials for the linear combination matrices of graphs, and we also characterize the bounds of these coefficients. These bounds implicitly encompass the existing results of Chan and Lam on trees and bipartite graphs. Furthermore, we give a solution to the open problem posed by Merris. Second, we characterize the first six coefficients of the hook immanantal polynomial. And the necessary and sufficient condition under which the linear combination matrices of two regular graphs have the same hook immanantal polynomial is proved. Third, we generalize the Frobenius–König theorem and the Laplace expansion theorem to immanants. Using these two theorems, we show that the star degree of a graph is always a lower bound for the multiplicity of a certain root of the immanantal polynomial of its linear combination matrix. Finally, we derive formulas for the first six coefficients of the hook immanantal polynomial for several important graph matrices. 2020 Mathematics Subject Classification 05B20, 05E05, 05C31, 05C50, 15A15. 1. Introduction Let \chi_{\lambda} be an irreducible character of the symmetric group \mathcal{S}_{n} , indexed by a partition \lambda of n . For an n\times n matrix M=[m_{ij}] , the immanant of M associated with \chi_{\lambda} is defined as (1) \displaystyle\operatorname{Imm}_{\lambda}(M)=\sum_{\sigma\in\mathcal{S}_{n}}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}m_{i\sigma(i)}. When \lambda=(k,1^{n-k}) , \operatorname{Imm}_{(k,1^{n-k})}(\cdot) is called the hook immanant . Bürgisser [ 5 ] proved that the computation of hook immanants with polynomially growing width is both #P-complete and VNP-complete. Schur [ 36 ] first considered immanants as generalized matrix functions. The determinant and permanent are immanants corresponding to the sign character and the trivial character, respectively, i.e., \operatorname{Imm}_{(1^{n})}(\cdot) and \operatorname{Imm}_{(n)}(\cdot) . Littlewood [ 25 ] pointed out that the immanant of a matrix is a multilinear function interpolating between the determinant and the permanent. Combinatorial and algebraic properties of immanants can be found in [ 2 , 19 , 20 , 22 , 26 , 38 ] . Let I_{n} denote the n\times n identity matrix. For an n\times n matrix M and an irreducible character \chi_{\lambda} , the immanantal polynomial of M associated with \chi_{\lambda} is defined as (2) \displaystyle\operatorname{Imm}_{\lambda}(xI_{n}-M)=\sum_{r=0}^{n}(-1)^{r}c_{\lambda,r}(M)\,x^{\,n-r}. In particular, • when \lambda=(k,1^{\,n-k}) , \operatorname{Imm}_{(k,1^{\,n-k})}(xI_{n}-M) is called the hook immanantal polynomial of M , • when \lambda=(1^{n}) , \operatorname{Imm}_{(1^{n})}(xI_{n}-M) is the characteristic polynomial of M , • when \lambda=(2,1^{\,n-2}) , \operatorname{Imm}_{(2,1^{\,n-2})}(xI_{n}-M) is the second immanantal polynomial of M , • when \lambda=(n) , \operatorname{Imm}_{(n)}(xI_{n}-M) is the permanent polynomial of M . For studies on immanantal polynomials of general matrices, see [ 4 , 29 ] . 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) . Denote by d_{G}(v_{i}) (simply d(v_{i}) ) the degree of vertex v_{i} . The degree matrix of G is D(G)=\mathrm{diag}(d(v_{1}),d(v_{2}),\ldots,d(v_{n})) . The adjacency matrix A(G)=[a_{ij}] is an n\times n (0,1) -matrix with a_{ij}=1 if v_{i}v_{j}\in E(G) and 0 otherwise. The matrix L(G)=D(G)-A(G) is the Laplacian matrix of G , and L(G)=D(G)+A(G) is the signless Laplacian matrix. The A_{\alpha}(G) matrix is defined as A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G) for \alpha\in[0,1] . In algebraic and combinatorics, the study on immanantal polynomials of graph matrices is a long-standing and classic problem. Merris [ 3 ] proved that almost all trees have complete immanantal polynomials. Yu and Qu [ 41 ] derived explicit expressions for the immanantal polynomials of the adjacency, Laplacian and signless Laplacian matrices of graphs. Cash [ 6 ] extended Sachs’ theorem to immanantal polynomials and applied it to chemical graphs such as hydrocarbon structures. Moreover, immanants have important applications in various theoretical and applied sciences [ 12 , 13 , 34 , 37 ] . Due to the computational complexity of immanants of graph matrices, relatively few results have been obtained. However, fruitful results exist for immanants under special partitions of graph matrices. Undoubtedly, the most abundant results are for determinants and permanents of graph matrices [ 1 , 4 , 11 , 17 , 18 , 24 , 32 , 33 , 39 ] . Merris [ 29 ] studied the second immanantal polynomials of the Laplacian matrices of graphs and proposed open problems concerning the bounds of its coefficients. Chan and Lam [ 7 , 10 ] characterized the bounds for the coefficients of the immanantal polynomials of the Laplacian matrices of trees, partially solving the problem. Meanwhile, Merris [ 29 ] also raised an open problem about the multiplicity of the root 1 of this polynomial, which was later solved by Wu et al. [ 40 ] . Chan and Lam [ 8 ] established a relationship between the third immanantal polynomial of the Laplacian matrix of a tree and its Wiener index. A natural question is: from the properties of immanant functions of graph matrices under special partitions (such as determinant and permanent), deduce the common properties that hold under all partitions. In this paper, we investigate this problem. This paper mainly studies the linear combination matrix \beta D(G)+\gamma A(G) of the degree matrix D(G) and the adjacency matrix A(G) of graph G , where \beta and \gamma are real numbers. Section 2 presents some definitions and lemmas. We introduce the concept of vertex orientation of the general graph and some important graph parameters. In Section 3 , using the tool of vertex orientation, we give a combinatorial interpretation of the coefficients of the immanantal polynomial of the linear combination matrix for general graphs. Furthermore, we characterize the upper and lower bounds for these coefficients. In addition, we determine the bounds for the coefficients of the immanantal polynomial of the linear combination matrix for trees and bipartite graphs, thereby generalizing the results of Chan and Lam. In Section 4 , we focus on the hook immanantal polynomial of the linear combination matrix for general graphs and give combinatorial interpretations of its first six coefficients. Using these coefficients, we prove the necessary and sufficient condition for two regular graphs to have equal hook immanantal polynomials of their linear combination matrices. Section 5 investigates the roots of the immanantal polynomial of the linear combination matrix. we generalize the Frobenius–König theorem and the Laplace expansion theorem to immanants. Applying these theorems, we prove that the star degree of a graph always provides a lower bound for the multiplicity of the root \beta in the immanantal polynomial of its linear combination matrix. In Section 6 , we further discuss Theorem 4.3 . We give the formulas for the first six coefficients of the hook immanantal polynomial for several important classes of graph matrices. Additionally, the classic known results of previous researchers can be derived. 2. Basic preliminaries In this section, we present some definitions and lemmas that will be used in the proofs of our results. Let G be a simple graph with vertex set V(G)=\{v_{1},v_{2},\ldots,v_{n}\} . The graph obtained by deleting the edge e from G is denoted by G-e . Denote by \mathfrak{D}(G) the degree sequence of G , i.e., \mathfrak{D}(G)=(d(v_{1}),d(v_{2}),\ldots,d(v_{n})) . Suppose \mathscr{C}_{l}(G) and \mathscr{M}_{l}(G) denote the sets of cycles of length l and l -matchings in G , respectively. Let \mathscr{T}_{j}(G) denote the sum of degrees of the three vertices on the j th triangle in \mathscr{C}_{3}(G) . If C=v_{i_{1}}v_{i_{2}}\cdots v_{i_{l}}v_{i_{1}}\in\mathcal{C}_{l}(G) , let \mathfrak{D}_{C}(G) be the degree sequence obtained from \mathfrak{D}(G) by deleting d(v_{i_{1}}) , d(v_{i_{2}}) ,…, d(v_{i_{l}}) . If \mathfrak{M}=\{v_{i_{1}}v_{i_{1}^{\prime}},v_{i_{2}}v_{i_{2}^{\prime}},\ldots,v_{i_{l}}v_{i_{l}^{\prime}}\}\in\mathscr{M}_{l}(G) , let \mathfrak{D}_{\mathfrak{M}}(G) be the degree sequence obtained from \mathfrak{D}(G) by deleting d(v_{i_{1}}) , d(v_{i_{1}^{\prime}}) , d(v_{i_{2}}) , d(v_{i_{2}^{\prime}}) ,…, d(v_{i_{l}}) , d(v_{i_{l}^{\prime}}) . Denote by F_{r} the r th elementary symmetric function , and define F_{r}(G)=F_{r}(\mathfrak{D}(G)) . For r\geq l , we define \displaystyle\mathcal{C}_{r}^{l}(G)=\sum_{C\in\mathscr{C}_{l}(G)}F_{r-l}(\mathfrak{D}_{C}(G)) and \displaystyle\mathcal{M}_{r}^{l}(G)=\sum_{\mathfrak{M}\in\mathscr{M}_{l}(G)}F_{r-2l}(\mathfrak{D}_{\mathfrak{M}}(G)). A pendant star of graph is defined as a maximal subgraph consisting of pendant edges, all incident to the same vertex (referred to as the center of the pendant star). A pendant vertex is a vertex with degree 1 . The degree of a pendant star is defined as the number of its pendant vertices minus one. The star degree of graph is defined as the sum of the degrees of all its pendant stars if such stars exist, otherwise, it is zero. Let C_{n} , P_{n} , S_{n} and K_{n} denote the cycle, path, star, and complete graph, respectively, each having n vertices. Chan and Lam [ 7 , 9 ] introduced the notion of the vertex orientations of trees and bipartite graphs. We extend this concept to general graphs. Let G be a graph, and let B is a subset of V(G) with r elements (or simply r -subset B of V(G) ). Assume that G[B] be the subgraph induced on B . For each vertex v in B , we assign an arrow pointing away from the vertex along one of its adjacent edges. There are d_{G}(v) ways to do this. We call such an assignment for all vertices in B a (B) -vertex orientation . In a (B) -vertex orientation, if there are r_{1} edges with 1 arrow, r_{2} edges with 2 arrows, r_{3} directed 3 -cycles, r_{4} directed 4 -cycles, and so on, then we say the (B) -vertex orientation is of type (\nu,B)=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\dots) , where r_{1}+2r_{2}+3r_{3}+4r_{4}+\dots=n . Define a_{G}(\nu,r) to be the number of (B) -vertex orientation of type (\nu,B) . For convenience, let \mathcal{P}(n) be the set of partitions of n , and let \mathcal{PB}(n) be the set of all partitions of n obtained from (B) -vertex orientation in G . We write \lambda\vdash n if \lambda is a partition of n . Given a positive integer n , let N_{r}=\{\{i_{1},i_{2},\ldots,i_{r}\}|1\leq i_{1}\leq i_{2}\leq\ldots\leq i_{r}\leq n\} . For I\in N_{r} , the subgroup (\mathcal{S}_{n})_{I} of the symmetric group \mathcal{S}_{n} is defined as \displaystyle(\mathcal{S}_{n})_{I}=\left\{\sigma\in\mathcal{S}_{n}\mid\sigma(i)=i\text{ for all }i\in\{1,\dots,n\}\setminus I\right\}. In particular, for a subset B=\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{r}}\} of V(G)=\{v_{1},v_{2},\ldots,v_{n}\} with an ordered sequence of indices 1\leq i_{1}0 and \gamma\leq|\beta| , then \beta D(G)+\gamma A(G) is a positive semidefinite Hermitian matrix. Lemma 2.4 . (Merris, [ 28 ] ) Let M_{1} and M_{2} be two n\times n matrices of the same structure. Then there exists a permutation matrix N such that \displaystyle\operatorname{Imm}_{\lambda}(M_{1})=\operatorname{Imm}_{\lambda}(N^{-1}M_{2}N). Lemma 2.5 . Let G be a graph. Then (3) \displaystyle a_{G}(\nu,r)\geq a_{G-e}(\nu,r). Proof. Since any (B) -vertex orientation of type (\nu,B) in G-e is also a (B) -vertex orientation of type (\nu,B) in G , the result in Lemma 2.5 can be directly obtained. ∎ Lemma 2.6 . (Chan and Lam, [ 10 ] ) Let T be a tree with n vertices. Then a_{S_{n}}(\nu,r)\leq a_{T}(\nu,r)\leq a_{p_{n}}(\nu,r). Lemma 2.7 . (Chan and Lam, [ 10 ] ) Let K_{p,q} denote the complete bipartite graph with (p,q) -bipartition, where p\geq q . Then a_{K_{p,q}}(\nu)>a_{K_{p+1,q-1}}(\nu). Lemma 2.8 . Let K_{p,q} denote the complete bipartite graph with (p,q) -bipartition, where p\geq q . Then \displaystyle a_{K_{p,q}}(\nu,r)>a_{K_{p+1,q-1}}(\nu,r). Proof. From Lemma 2.7 and the definition of (B) -vertex orientation, we can directly obtain the result in Lemma 2.8 . ∎ Lemma 2.9 . (Sagan, [ 35 ] ) Let \lambda and \alpha=(\alpha_{1},\ldots,\alpha_{i}) be two partitions. Then \displaystyle\chi_{\lambda}(\alpha)=\sum_{\xi}(-1)^{h(\xi)}\chi_{\lambda/\xi}(\alpha/\alpha_{1}), where the sum runs over all rim hooks \xi of length \alpha_{1} in \lambda , and h(\xi)=(\text{number of rows of }\xi)-1 . Lemma 2.10 . (Sagn, [ 35 ] ) Suppose \sigma_{1}\oplus\sigma_{2}\in\mathcal{S}_{r}\times\mathcal{S}_{n-r}\subseteq\mathcal{S}_{n} , \lambda\vdash n , \mu\vdash r and \nu\vdash n-r . Then \displaystyle\chi_{\lambda}(\sigma_{1}\oplus\sigma_{2}) \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mu\vdash r\\ \nu\vdash n-r\end{subarray}}c_{\mu,\nu}^{\lambda}\;\chi_{\mu}(\sigma_{1})\,\chi_{\nu}(\sigma_{2}), where c_{\mu,\nu}^{\lambda} are Littlewood–Richardson coefficients. Lemma 2.11 . (James and Kerber, [ 21 ] ) Let \chi_{(k,1^{n-k})} be the irreducible character of the symmetric group \mathcal{S}_{n} indexed by the partition (k,1^{n-k}) . Let id denote the identity permutation of \mathcal{S}_{n} . Then \displaystyle\chi_{(k,1^{n-k})}(\text{id})=\binom{n-1}{k-1}. Lemma 2.12 . Let \sigma be a permutation in the symmetric group \mathcal{S}_{n} with cycle type (\sigma)=(l,1^{n-l}) . Then \displaystyle\chi_{(k,1^{n-k})}(\sigma)=\binom{n-l-1}{k-l-1}+(-1)^{l-1}\binom{n-l-1}{k-1}. Proof. By Lemma 2.9 and Lemma 2.11 , we obtain \displaystyle\chi_{(k,1^{n-k})}(l,1^{n-l}) \displaystyle= \displaystyle\chi_{(k-l,1^{n-k})}(1^{n-l})+(-1)^{l-1}\chi_{(k,1^{n-k-l})}(1^{n-l}) \displaystyle= \displaystyle\binom{n-l-1}{k-l-1}+(-1)^{l-1}\binom{n-l-1}{k-1}. The proof of Lemma 2.12 is complete. ∎ 3. Bounds on coefficients In this section, we characterize the explicit formulas for the coefficients of the immanantal polynomials of the linear combination matrices of graphs by applying (B) -vertex orientation. And the upper and lower bounds for these coefficients is determined. Moreover, we determine the bounds for the coefficients of the immanantal polynomials of the linear combination matrices for trees and bipartite graphs. Meanwhile, we also deduce the existing results of Chan and Lam on trees and bipartite graphs, and we solve the open problem proposed by Merris. 3.1. Bounds for the coefficients of the immanantal polynomials of the linear combination matrices of graphs Prior to the introduction of our main results, we establish several lemmas. Lemma 3.1 . Let G be a graph with n vertices, and let the matrix \beta D(G)+\gamma A(G)=[h_{ij}] , where \beta and \gamma be two non-zero real numbers. Then \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\sum\limits_{B:|B|=r,B\subseteq V(G)}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod_{i=1}^{n}h_{i\sigma(i)} \displaystyle= \displaystyle\sum\limits_{B:|B|=r,B\subseteq V(G)}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\beta^{\mathcal{F}(\sigma)}\gamma^{n-\mathcal{F}(\sigma)}\prod\limits_{v_{i}\in B,\sigma(i)=i}d(v_{i}), where \mu is a conjugate class of the subgroup (\mathcal{S}_{n})_{B} , and \mathcal{F}(\sigma) is the number of fixed points in \sigma . Proof. Suppose that G is a graph with vertices v_{1},v_{2},\ldots,v_{n} . Index the rows and columns of the matrix \beta D(G)+\gamma A(G) by v_{1},v_{2},\ldots,v_{n} . For convenience, we use H(G)=[h_{ij}] to denote \beta D(G)+\gamma A(G) . By Lemma 2.1 , we have \displaystyle c_{\lambda,r}(H(G)) \displaystyle= \displaystyle\sum_{B:|B|=r,B\subseteq V(G)}\sum_{\sigma\in(\mathcal{S}_{n})_{B}}\chi_{\lambda}(\sigma)\prod_{v_{i}\in B}h_{i\sigma(i)} \displaystyle= \displaystyle\sum_{B:|B|=r,B\subseteq V(G)}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod_{i=1}^{n}h_{i\sigma(i)}, where C is a conjugate class of the subgroup (\mathcal{S}_{n})_{B} . Assume that B=\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{r}}\} with 1\leq i_{1}\leq i_{2}\leq\cdots\leq i_{r}\leq n . Let \mathcal{S}_{B} be the set of permutations on the indices of the vertices in B , and let G[B] be the subgraph induced on B . In fact, we only consider the case that the term \prod\limits_{i}h_{i\sigma(i)} is non-zero. For any \sigma\in(\mathcal{S}_{n})_{B} , we have \sigma(i)=i for v_{i}\in\{v_{1},v_{2},\ldots,v_{n}\}\setminus B . Thus, for any \sigma\in(\mathcal{S}_{n})_{B} , there exists a unique permutation \sigma^{\prime}\in\mathcal{S}_{B} such that \sigma(i)=\sigma^{\prime}(i) for v_{i}\in B . Then \sigma\in(\mathcal{S}_{n})_{B} and \sigma^{\prime}\in\mathcal{S}_{B} are in one-to-one correspondence. Therefore, it suffices to consider permutations in \mathcal{S}_{B} . The term h_{i\sigma(i)}\neq 0 if and only if \sigma(i)=i or \sigma(i)\neq i and (i,\sigma(i))\in E(G) . Let \sigma=(j_{1}j_{2}\cdots j_{s})(j_{s+1}\cdots j_{t})\cdots(j_{m})(j_{m+1})\cdots(j_{r})\in\mathcal{S}_{B} be a product of disjoint cycles such that \prod\limits_{v_{i}\in B}h_{i\sigma(i)}\neq 0 . Cycles of length 3 or more in \sigma correspond to cycles of the same length in G[B] . A transposition in \sigma corresponds to an edge in G[B] . Let B_{1}\subseteq B be the set of fixed vertices under \sigma . Let B_{2} be the set of edges in G[B] corresponding to the transpositions in the disjoint cycle factorization of \sigma . Let B_{3},B_{4},\ldots,B_{t} be all graph cycles in G[B] corresponding to cycles of length greater than 2 in the disjoint cycle factorization of \sigma . Note that if v_{i}\in B , then \sigma(i)\in B for \sigma\in\mathcal{S}_{B} . Any 2 -cycle (i,j) in \sigma corresponds to the non-zero factor h_{ij}h_{ji} , i.e., v_{i}v_{j}\in E(G) . Any l -cycle (j_{1}j_{2}\cdots j_{l}) in \sigma corresponds to the non-zero factor h_{j_{1}j_{2}}h_{j_{2}j_{3}}\cdots h_{j_{l}j_{1}} , meaning that v_{j_{1}}v_{j_{2}}\cdots v_{j_{t}}v_{j_{1}} is a graph cycle of girth r in G . Therefore, we have \displaystyle\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod_{v_{i}\in B}h_{i\sigma(i)} \displaystyle= \displaystyle\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\left(\prod_{v_{i}\in B_{1}}h_{ii}\prod_{e=(v_{i},v_{\sigma(i}))\in B_{2}}h_{i\sigma(i)}^{2}\prod_{e=(v_{i},v_{\sigma(i)})\in B_{3}}h_{i,\sigma(i)}\cdots\prod_{e=(v_{i},v_{\sigma(i)})\in B_{t}}h_{i,\sigma(i)}\right) \displaystyle= \displaystyle\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\beta^{|B_{1}|}\gamma^{n-|B_{1}|}\prod_{v_{i}\in B_{1}}d(v_{i}) \displaystyle= \displaystyle\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\beta^{\mathcal{F}(\sigma)}\gamma^{n-\mathcal{F}(\sigma)}\prod_{v_{i}\in B:i=\sigma(i)}d(v_{i}). This completes the proof. ∎ From Lemma 3.1 , we derive formulas for the immanantal polynomial coefficients of the Laplacian matrix, the signless Laplacian matrix, and the A_{\alpha} matrix of a graph. For a more concise and elegant form, the formula for the coefficients corresponding to the A_{\alpha} matrix is given as follows. Corollary 3.2 . Let G be an n -vertex graph. If \alpha\notin\{0,1\} , then \displaystyle c_{\lambda,r}(A_{\alpha}(G))=(1-\alpha)^{n}\sum\limits_{B:|B|=r,B\subseteq V(G)}\sum\limits_{C}\chi_{\lambda}(C)\sum\limits_{\sigma\in C}(\frac{\alpha}{1-\alpha})^{\mathcal{F}(\sigma)}\prod\limits_{v_{i}\in B;\sigma(i)=i}d(v_{i}), where C is a conjugacy class of the subgroup (\mathcal{S}_{n})_{B} , and \mathcal{F}(\sigma) is the number of fixed points in \sigma . The relationship between \sum\limits_{\sigma\in(\mathcal{S}_{n})_{B}\atop\text{type}(\sigma)=\mu}\prod\limits_{i=1}^{n}h_{i\sigma(i)} in Lemma 3.1 and a_{G}(\nu,r) is further clarified as follows. Lemma 3.3 . Let G be a graph with n vertices, and let \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots)\in\mathcal{P}(n) . Then for each r -subset B of vertices of G , \sum\limits_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod\limits_{i=1}^{n}h_{i\sigma(i)}=\beta^{t_{1}}\gamma^{n-t_{1}}\sum_{\nu\in\mathcal{PB}(n)}\binom{\nu}{\mu}a_{G}(\nu,r), where \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) with r_{i}\geq t_{i} for all i=2,3,4,5,\ldots , and \binom{\nu}{\mu}=\binom{r_{2}}{t_{2}}\binom{r_{3}}{t_{3}}\binom{r_{4}}{t_{4}}\cdots . Proof. Given B , we count the set \mathscr{O}_{\mu}=\{(\sigma,O):type(\sigma)=\mu,O\text{ is a }(B)\text{-vertex orientation associated with }\sigma\}. Given a \sigma\in(\mathcal{S}_{n})_{B} with type (\sigma)=\mu , we can form a (B) -vertex orientation O . The construction proceeds as follows: given a cycle (a_{1}a_{2}\dots a_{l}) with l>2 in a permutation \sigma\in(\mathcal{S}_{n})_{B} , we orient the corresponding edges in G[B] to form a directed cycle-specifically, from v_{a_{i}} to v_{a_{i+1}} for i=1,\dots,l-1 , and finally from v_{a_{l}} to v_{a_{1}} . When the cycle is a transposition (a_{1}a_{2}) ( l=2 ), we place two arrows on the edge \{v_{a_{1}},v_{a_{2}}\} , pointing in opposite directions. By this construction, a (B) -vertex orientation O is derived. Clearly, (\sigma,O)\in\mathscr{O}_{\mu} . This implies that (4) \displaystyle\sum\limits_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu,}\prod\limits_{i=1}^{n}h_{i\sigma(i)}=\beta^{t_{1}}\gamma^{r-t_{1}}|\mathfrak{M}_{\mu}|. Given a (B) -vertex orientation O of type \nu . There are \binom{r_{2}}{t_{2}} ways to pick t_{2} independent edges, \binom{r_{3}}{t_{3}} ways to pick t_{3} 3 -cycles and so on. Each choice of edges and cycles corresponds to a permutation \sigma\in(\mathcal{S}_{n})_{B} of cycle type \mu . So there are \binom{r_{2}}{t_{2}}\binom{r_{3}}{t_{3}}\binom{r_{4}}{t_{4}}\cdots ways to form the ordered pair (\sigma,O) . Hence, (5) \displaystyle|\mathscr{O}_{\mu}|=\sum_{\nu\in\mathcal{PB}(n)}\binom{\nu}{\mu}a_{G}(\nu,r), Combining Equations ( 11 ) and ( 12 ), we have \sum\limits_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod\limits_{i=1}^{n}h_{i\sigma(i)}=\beta^{t_{1}}\gamma^{r-t_{1}}\sum_{\nu\in\mathcal{PB}(n)(n)}\binom{\nu}{\mu}a_{G}(\nu,r). This completes the proof. ∎ This allows us to rewrite c_{\lambda,r}(\beta D(G)+\gamma A(G)) in terms of a_{G}(\nu,r) . Lemma 3.4 . Let G be an n -vertex graph. Then \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{G}(\nu,r)\beta^{t_{1}}\gamma^{r-t_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}, where \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) are two partitions in \mathcal{P}(n) satisfying r_{i}\geq t_{i} for all i=2,3,4,5,\ldots . Proof. From Lemma 3.1 and Lemma 3.3 , we obtain \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\sum\limits_{B:|B|=r,B\subseteq V(G)}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\sum_{\sigma\in(\mathcal{S}_{n})_{B}\atop type(\sigma)=\mu}\prod_{i=1}^{n}h_{i\sigma(i)} \displaystyle= \displaystyle\sum\limits_{B:|B|=r,B\subseteq V(G)}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\beta^{t_{1}}\gamma^{r-t_{1}}\sum_{\nu\in\mathcal{PB}(n)}\binom{\nu}{\mu}a_{G}(\nu,r) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{G}(\nu,r)\beta^{t_{1}}\gamma^{r-t_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}. We have completed the proof of Lemma 3.4 . ∎ Lemma 3.5 . (Chan and Lam, [ 9 ] ) Let \chi_{\lambda}(\mu) be an irreducible character of \mathcal{S}_{n} . Given a partition \nu of n , we have \sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}\geq 0. Lemma 3.6 . Let T be a tree with n vertices. If \beta>0 and \gamma\neq 0 , then \displaystyle c_{\lambda,r}(\beta D(T)+\gamma A(T))\geq c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n})). Proof. Let \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) be two partitions in \mathcal{P}(n) satisfying r_{i}\geq t_{i} for all i=2,3,4,5,\ldots . For a tree T , we only consider \mu=(1^{t_{1}},2^{t_{2}}) and \nu=(1^{r_{1}},2^{r_{2}}) , with r_{2}\geq t_{2} . Note that t_{1}+2t_{2}=n . According to Lemma 3.4 , we have \displaystyle c_{\lambda,r}(\beta D(T)+\gamma A(T)) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{T}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}. From Lemma 2.6 , \beta>0 and \gamma\neq 0 , we deduce \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{T}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle\leq \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{S_{n}}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}. This implies c_{\lambda,r}(\beta D(T)+\gamma A(T))\geq c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n})) . ∎ Lemma 3.7 . Let G be a graph, and let G_{1} be a subgraph of G with V(G_{1})=V(G) . If \beta>0 and \gamma\geq-\beta , then \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G))\geq c_{\lambda,r}(\beta D(G_{1})+\gamma A(G_{1})). Proof. According to the value of \gamma , we consider two following cases. Case 1. Assume that -\beta\leq\gamma\leq 0 . Given that H(G)=\beta D(G)+\gamma A(G) and H(G_{1})=\beta D(G_{1})+\gamma A(G_{1}) , consider an r\times r principal submatrix H_{1} of H(G_{1}) , whose rows and columns are indexed by a vertex subset R\subseteq V(G_{1}) . Define G[R] to be the subgraph of G induced by R , and G_{1}[R] as the corresponding induced subgraph of G_{1} . Then \displaystyle H_{1}=H(G_{1}[R])+D^{R}_{1}, where D^{R}_{1} is a nonnegative diagonal matrix, whose entries may be zero. Each main diagonal element of D^{R}_{1} counts the number of edges joining the corresponding vertex in G_{1} to a vertex outside R . Now define G_{2}[R] as the graph on vertex set R containing exactly those edges of G[R] that are missing in G_{1}[R] . Then \displaystyle H(G[R])=H(G_{1}[R])+H(G_{2}[R]). Finally, the principal submatrix H of H(G) that corresponds to the vertex set R is given by \displaystyle H=H(G[R])+D^{R}, where D^{R} is a nonnegative diagonal matrix. Every main diagonal entry of D^{R}_{1} denotes the number of edges that connect the corresponding vertex in G_{1} to a vertex not contained in R . It follows that \displaystyle H=H_{1}+H(G_{2}[R])+(D^{R}-D^{R}_{1}), Since G_{1} is a subgraph of G , D^{R}-D^{R}_{1} is a diagonal matrix with nonnegative entries. By Lemma 2.3 , we obtain that H(G_{2}[R]) is a positive semi-definite hermitian matrix. This indicate that H(G_{2}[R])+(D^{R}-D^{R}_{1}) is a positive semi-definite hermitian matrix. Applying Lemma 2.2 , we get d_{\lambda}(H)\geq d_{\lambda}(H_{1}) . This implies that we have derived a one-to-one correspondence between the r\times r principal submatrices H_{1} of H(G_{1}) and some of the r\times r principal submatrices H of H(G) such that d_{\lambda}(H)\geq d_{\lambda}(H_{1}) . Thus, c_{\lambda,r}(\beta D(G)+\gamma A(G))\geq c_{\lambda,r}(\beta D(G_{1})+\gamma A(G_{1})) . Case 2. Assume that \gamma>0 . Let \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) be two partitions in \mathcal{P}(n) with r_{i}\geq t_{i} for all i=2,3,4,5,\ldots . Since \beta>0 and \gamma>0 , we have \beta^{t_{1}}\gamma^{r-t_{1}}\geq 0 . By Equation ( 13 ), Lemma 3.5 and Lemma 2.5 , we have \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{G}(\nu,r)\beta^{t_{1}}\gamma^{k-t_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle\geq \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{G-e}(\nu,r)\beta^{t_{1}}\gamma^{k-t_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle= \displaystyle c_{\lambda,r}(\beta D(G-e)+\gamma A(G-e)). It means that c_{\lambda,r}(\beta D(G)+\gamma A(G))\geq c_{\lambda,r}(\beta D(G_{1})+\gamma A(G_{1})) . Based the above arguments, we complete the proof. ∎ Theorem 3.8 . Assume that G is a graph with n vertices. If \beta>0 , \gamma\geq-\beta and \gamma\neq 0 , then c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n}))\leq c_{\lambda,r}(\beta D(G)+\gamma A(G))\leq c_{\lambda,r}(\beta D(K_{n})+\gamma A(K_{n})). Proof. Let T be a spanning tree of G of order n . By Lemma 3.6 , we have c_{\lambda,r}(\beta D(T)+\gamma A(T))\geq c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n})) . Note that T is a subgraph of G and G is a subgraph of K_{n} . By Lemma 3.7 , we obtain c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n}))\leq c_{\lambda,r}(\beta D(G)+\gamma A(G))\leq c_{\lambda,r}(\beta D(K_{n})+\gamma A(K_{n})) . ∎ Using Theorem 3.8 , we can obtain the upper and lower bounds for c_{\lambda,r}(L(G)) . Corollary 3.9 . Let G be a graph on n vertices. Then \displaystyle c_{\lambda,r}(L(S_{n}))\leq c_{\lambda,r}(L(G))\leq c_{\lambda,r}(L(K_{n})). Merris [ 29 ] proposed an open problem concerning the coefficients of the second immanantal polynomial of the Laplacian matrix of a graph: characterize the maximum and minimum values of c_{(2,1^{n-2}),r}(L(G)) . Corollary 3.9 provides a solution to this problem. Moreover, Merris et al. [ 31 ] gave the minimum and maximum values of the permanent of the Laplacian matrix of a graph, which can be directly obtained from Corollary 3.9 . Corollary 3.10 . (Merris et al., [ 31 ] ) Let G be a graph with n vertices. Then \displaystyle\operatorname{per}(L(S_{n}))\leq\operatorname{per}(L(G))\leq\operatorname{per}(L(K_{n})). Applying Theorem 3.8 , we can also obtain upper and lower bounds for c_{\lambda,r}(Q(G)) and c_{\lambda,r}(A_{\alpha}(G)) . Corollary 3.11 . Let G be a graph on n vertices. Then \displaystyle c_{\lambda,r}(Q(S_{n}))\leq c_{\lambda,r}(Q(G))\leq c_{\lambda,r}(Q(K_{n})). Corollary 3.12 . Let G be a graph with n vertices. If \alpha\notin\{0,1\} , then \displaystyle c_{\lambda,r}(A_{\alpha}(S_{n}))\leq c_{\lambda,r}(A_{\alpha}(G))\leq c_{\lambda,r}(A_{\alpha}(K_{n})). 3.2. Bounds for the coefficients of the immanantal polynomial of the Linear combination matrix for trees and bipartite graphs When G is a tree or a bipartite graph, we use the (B) -vertex orientation method to give bounds for the coefficient c_{\lambda,r}(\beta D(G)+\gamma A(G)) . Theorem 3.13 . Let T be a tree with n vertices. If \beta>0 and \gamma\neq 0 , then c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n}))\leq c_{\lambda,r}(\beta D(T)+\gamma A(T))\leq c_{\lambda,r}(\beta D(P_{n})+\gamma A(P_{n})). Proof. The left inequality follows directly from Lemma 3.6 . Now we prove the right inequality. Similarly, let \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) be two partitions in \mathcal{P}(n) satisfying r_{i}\geq t_{i} for all i=2,3,4,5,\ldots . For a tree T , we only consider \mu=(1^{t_{1}},2^{t_{2}}) and \nu=(1^{r_{1}},2^{r_{2}}) , with r_{2}\geq t_{2} . Note that t_{1}+2t_{2}=n . According to Theorem 3.4 , we have \displaystyle c_{\lambda,r}(\beta D(T)+\gamma A(T)) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{T}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu}\chi_{\lambda}(\mu)\binom{\nu}{\mu}. From Lemma 2.6 , \beta>0 and \gamma\neq 0 , we deduce \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{T}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle\leq \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{p_{n}}(\nu,r)\beta^{m_{1}}\gamma^{2m_{2}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu}. This implies c_{\lambda,r}(\beta D(T)+\gamma A(T))\leq c_{\lambda,r}(\beta D(P_{n})+\gamma A(P_{n})) . The proof is complete. ∎ Chan and Lam [ 10 ] gave upper and lower bounds for the coefficients of the immanantal polynomial of the Laplacian matrix of trees. This is a direct corollary of Theorem 3.13 . Corollary 3.14 (Chan and Lam, [ 10 ] ) . Let T be a tree on n vertices. Then \displaystyle c_{\lambda,r}(L(S_{n}))\leq c_{\lambda,r}(L(T))\leq c_{\lambda,r}(L(P_{n})). The upper and lower bounds for c_{\lambda,r}(A_{\alpha}(T)) can be obtained from Theorem 3.13 . Corollary 3.15 . Let T be a tree with n vertices. If \alpha\notin\{0,1\} , then \displaystyle c_{\lambda,r}(A_{\alpha}(S_{n}))\leq c_{\lambda,r}(A_{\alpha}(T))\leq c_{\lambda,r}(A_{\alpha}(P_{n})). Theorem 3.16 . Let G be a bipartite graph with n vertices. If \beta>0 and \gamma\neq 0 , then c_{\lambda,k}(\beta D(S_{n})+\gamma A(S_{n}))\leq c_{\lambda,k}(\beta D(G)+\gamma A(G))\leq c_{\lambda,k}(\beta D(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})+\gamma A(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})) Proof. Let \mu=(1^{t_{1}},2^{t_{2}},3^{t_{3}},4^{t_{4}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},3^{r_{3}},4^{r_{4}},\ldots) be two partitions in \mathcal{P}(n) satisfying r_{i}\geq t_{i} for all i=2,3,4,5,\ldots . Since G is bipartite, we only consider partitions \mu=(1^{t_{1}},2^{t_{2}},4^{t_{4}},6^{t_{6}},\ldots) and \nu=(1^{r_{1}},2^{r_{2}},4^{r_{4}},6^{r_{6}},\ldots) , with n_{i}\geq m_{i} for all i=2,4,6,\ldots . Note that t_{1}+2t_{2}+4t_{4}+6t_{6}+\cdots=n , so it is easy to see that n-t_{1} is even. Since \beta>0 and \gamma\neq 0 , we have \beta^{t_{1}}\gamma^{n-t_{1}}>0 . Suppose G has a (p,q) -bipartition. From Lemma 2.5 , we deduce a_{G}(\nu,r)\leq a_{K_{p,q}}(\nu,r) . By Lemma 2.8 , we have a_{K_{p,q}}(\nu,r)\leq a_{K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}}(\nu,r) . This implies (6) \displaystyle a_{G}(\nu,r)\leq a_{K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}}(\nu,r). From equation ( 13 ), ( 6 ), and Lemma 3.5 , we obtain (7) \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{G}(\nu,r)\beta^{m_{1}}\gamma^{k-m_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle\leq \displaystyle\sum_{\nu\in\mathcal{P}(n)}a_{K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}}(\nu,r)\beta^{m_{1}}\gamma^{k-m_{1}}\sum_{\mu\in\mathcal{P}(n)}\chi_{\lambda}(\mu)\binom{\nu}{\mu} \displaystyle= \displaystyle c_{\lambda,r}(\beta D(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})+\gamma A(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor})). Let T be a spanning tree of G of order n . By Theorem 3.13 , we have c_{\lambda,r}(\beta D(T)+\gamma A(T))\geq c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n})) . Note that T is a subgraph of G . By Lemma 2.5 , we obtain (8) \displaystyle c_{\lambda,r}(\beta D(G)+\gamma A(G))\geq c_{\lambda,r}(\beta D(S_{n})+\gamma A(S_{n})). Combining Equations ( 7 ) and ( 8 ) yields the desired result. This completes the proof of Theorem 3.16 . ∎ By applying Theorem 3.16 , we obtain upper and lower bounds for c_{\lambda,r}(L(G)) and c_{\lambda,r}(A_{\alpha}(G)) . Corollary 3.17 (Chan and Lam, [ 9 ] ) . Let G be a bipartite graph on n vertices. Then \displaystyle c_{\lambda,r}(L(S_{n}))\leq c_{\lambda,r}(L(G))\leq c_{\lambda,r}(L(K_{\lceil n/2\rceil,\lfloor n/2\rfloor})). Corollary 3.18 . Let G be a bipartite graph on n vertices. If \alpha\notin\{0,1\} , then \displaystyle c_{\lambda,r}(A_{\alpha}(S_{n}))\leq c_{\lambda,r}(A_{\alpha}(G))\leq c_{\lambda,r}(A_{\alpha}(K_{\lceil n/2\rceil,\lfloor n/2\rfloor})). 4. The necessary and sufficient conditions for the equality of hook immanantal polynomials of linear combination matrices of regular graphs In this section, we first characterize the first six coefficients of the hook immanantal polynomials for the linear combination matrices of graphs. Using these coefficients, we prove that the hook immanantal polynomials of the linear combination matrices of two regular graphs are equal if and only if those of their adjacency matrices are equal. Before presenting the main results, we introduce two important lemmas. Lemma 4.1 . Let i be a positive integer. Then \displaystyle\chi_{(k,1^{n-k})}(2^{i},1^{n-2i})=\sum\limits_{j=0}^{i}(-1)^{j}\binom{n-2i-1}{k-2i+2j-1}\binom{i}{j}=\sum\limits_{j=0}^{i}(-1)^{j}\binom{n-2i-1}{n-k-2j}\binom{i}{j}. Proof. By Lemma 2.9 , we have (9) \displaystyle\chi_{(k,1^{n-k})}(2^{i},1^{n-2i}) \displaystyle= \displaystyle\chi_{(k-2,1^{n-k})}(2^{i-1},1^{n-2i})-\chi_{(k,1^{n-k-2})}(2^{i-1},1^{n-2i}) \displaystyle= \displaystyle\chi_{(k-4,1^{n-k})}(2^{i-2},1^{n-2i})-2\chi_{(k-2,1^{n-k-2})}((2^{i-2},1^{n-2i}))+\chi_{(k,1^{n-k-4})}(2^{i-2},1^{n-2i}) \displaystyle= \displaystyle\chi_{(k-6,1^{n-k})}(2^{i-3},1^{n-2i})-3\chi_{(k-4,1^{n-k-2})}(2^{i-3},1^{n-2i}) \displaystyle+3\chi_{(k-2,1^{n-k-4})}(2^{i-3},1^{n-2i})+\chi_{(k,1^{n-k-6})}(2^{i-3},1^{n-2i}) \displaystyle= \displaystyle\chi_{(k-8,1^{n-k})}(2^{i-4},1^{n-2i})-4\chi_{(k-6,1^{n-k-2})}(2^{i-4},1^{n-2i})+6\chi_{(k-4,1^{n-k-4})}(2^{i-4},1^{n-2i}) \displaystyle-4\chi_{(k-2,1^{n-k-6})}(2^{i-4},1^{n-2i})+\chi_{(k,1^{n-k-8})}(2^{i-4},1^{n-2i}) \displaystyle= \displaystyle\cdots \displaystyle= \displaystyle\binom{i}{0}\cdot\chi_{(k-2i,1^{n-k})}(1^{n-2i})-\binom{i}{1}\cdot\chi_{(k-2i+2,1^{n-k-2})}(1^{n-2i}) \displaystyle+\binom{i}{2}\cdot\chi_{(k-2i+4,1^{n-k-4})}(1^{n-2i})+\cdots+(-1)^{j}\binom{i}{j}\cdot\chi_{(k-2i+2j,1^{n-k-2j})}(1^{n-2i}) \displaystyle+\cdots+(-1)^{i-1}\binom{i}{i-1}\cdot\chi_{(k-2,1^{n-k-2i+2})}((1^{n-2i}))+(-1)^{i}\binom{i}{i}\cdot\chi_{(k,1^{n-k-2i})}(1^{n-2i}) \displaystyle= \displaystyle\sum\limits_{j=0}^{i}(-1)^{j}\binom{i}{j}\cdot\chi_{(k-2i+2j,1^{n-k-2j})}(1^{n-2i}). By Lemma 2.11 , we obtain (10) \displaystyle\chi_{(k-2i+2j,1^{n-k-2j})}(1^{n-2i})=\binom{n-2i-1}{k-2i+2j-1}=\binom{n-2i-1}{n-k-2j}. Combining Equations ( 11 ) and ( 12 ), we have \displaystyle\chi_{(k,1^{n-k})}(2^{i},1^{n-2i})=\sum\limits_{j=0}^{i}(-1)^{j}\binom{n-2i-1}{n-k-2j}\binom{i}{j}. This completes the proof. ∎ Lemma 4.2 . Let \sigma be a permutation in the symmetric group \mathcal{S}_{n} of type (\sigma)=(3,2,1^{n-5}) . Then \displaystyle\chi_{(k,1^{n-k})}(\sigma)=\binom{n-6}{k-6}-\binom{n-6}{k-4}+\binom{n-6}{k-3}-\binom{n-6}{k-1}. Proof. By Lemma 2.9 and Lemma 2.11 , we obtain \displaystyle\chi_{(k,1^{n-k})}(3,2,1^{n-5}) \displaystyle= \displaystyle\chi_{(k-3,1^{n-k})}(2,1^{n-5})+\chi_{(k,1^{n-k-3})}(2,1^{n-5}) \displaystyle= \displaystyle\chi_{(k-5,1^{n-k})}(1^{n-5})-\chi_{(k-3,1^{n-2-k})}(1^{n-5})+\chi_{(k-2,1^{n-k-3})}(1^{n-5})-\chi_{(k,1^{n-k-5})}(1^{n-5}) \displaystyle= \displaystyle\binom{n-6}{k-6}-\binom{n-6}{k-4}+\binom{n-6}{k-3}-\binom{n-6}{k-1}. We have completed the proof. ∎ Theorem 4.3 . Let G be a graph with n vertices and m edges, and (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle\operatorname{Imm}_{(k,1^{n-k})}(xI-\beta D(G)-\gamma A(G))=\sum_{r=0}^{n}(-1)^{r}c_{(k,1^{n-k}),r}(\beta D(G)+\gamma A(G))x^{n-r}. Then \displaystyle c_{(k,1^{n-k}),0}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),1}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle F_{1}(G)\binom{n-1}{k-1}=2m\beta\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),2}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\beta^{2}F_{2}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)m\gamma^{2}}{k-1}\binom{n-2}{k-2}\quad(n\geq 3), \displaystyle c_{(k,1^{n-k}),3}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\beta^{3}F_{3}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta\gamma^{2}\mathcal{M}_{3}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2|\mathscr{C}_{3}(G)|\gamma^{3}\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]\quad(n\geq 4), \displaystyle c_{(k,1^{n-k}),4}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\beta^{4}F_{4}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta^{2}\gamma^{2}\mathcal{M}_{4}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+\beta\gamma^{3}\mathcal{C}_{4}^{3}(G)\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]+2|\mathscr{C}_{4}(G)|\gamma^{4}\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\bigg[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\bigg]\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]\gamma^{4}\quad(n\geq 5), and \displaystyle c_{(k,1^{n-k}),5}(\beta D(G)+\gamma A(G)) \displaystyle= \displaystyle\beta^{5}F_{5}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta^{3}\gamma^{2}\mathcal{M}_{5}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2\beta^{2}\gamma^{3}\mathcal{C}_{5}^{3}(G)\bigg[\binom{n-4}{k-4}+\binom{n-4}{k-1}\bigg]+2\beta\gamma^{4}\mathcal{C}_{5}^{4}(G)\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\beta\gamma^{4}\mathcal{M}_{5}^{2}(G)\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]+2|\mathscr{C}_{5}(G)|\gamma^{5}\bigg[\binom{n-6}{k-6}-\binom{n-6}{k-1}\bigg] \displaystyle+\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}2(m+3-\mathscr{T}_{j}(G))\gamma^{5}\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg]\quad(n\geq 6). Proof. From Equation ( 1 ) with M=xI-\beta D(G)-\gamma A(G) , we get c_{(k,1^{n-k}),0}(\beta D(G)+\gamma A(G))=\chi_{(k,1^{n-k})}(\text{id}) . By Lemma 2.11 , we obtain c_{(k,1^{n-k}),0}(\beta D(G)+\gamma A(G))=\binom{n-1}{k-1} . The coefficient c_{(k,1^{n-k}),1}(\beta D(G)+\gamma A(G)) is \chi_{(k,1^{n-k})}(\text{id}) multiplied by the trace of matrix \beta D(G)+\gamma A(G) . By Lemma 2.11 , we have c_{(k,1^{n-k}),1}(\beta D(G)+\gamma A(G))=F_{1}(G)\chi_{(k,1^{n-k})}(\text{id})=F_{1}(G)\binom{n-1}{k-1}=2m\beta\binom{n-1}{k-1} . If n\geq 3 , contributions to x^{n-2} come from two sources. The first is \sigma=\text{id} , accounting for the term \beta^{2}F_{2}(G)\binom{n-1}{k-1} . The second source is the set of transpositions that swap vertices forming an edge. In this case, by Lemma 4.1 , the value of \chi_{(k,1^{n-k})} is \frac{2k-n-1}{k-1}\binom{n-2}{k-2} . So, c_{(k,1^{n-k}),2}(\beta D(G)+\gamma A(G))=\beta^{2}F_{2}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)m\gamma^{2}}{k-1}\binom{n-2}{k-2}. To complete the proof, it suffices to establish the following claim. Claim 4.1 . The contribution of an l -cycle to c_{(k,1^{n-k}),r}(\beta D(G)+\gamma A(G)) is \displaystyle 2|\mathscr{C}_{l}(G)|\gamma^{l}\bigg[\binom{n-l-1}{k-l-1}+(-1)^{l-1}\binom{n-l-1}{k-1}\bigg]. Proof of Claim 4.1 . This term comes from an l -cycle \sigma=(i_{1}i_{2}\cdots i_{l}) , for which v_{i_{1}}v_{i_{2}} , v_{i_{2}}v_{i_{3}} , …, v_{i_{l-1}}v_{i_{l}} and v_{i_{l}}v_{i_{1}} are all edges of G . By Lemma 2.12 , the value of \chi_{(k,1^{n-k})} on the l -cycle \sigma is given by \binom{n-l-1}{k-l-1}+(-1)^{l-1}\binom{n-l-1}{k-1} . Note that the inverse of an l -cycle is also an l -cycle, so we deduce that each l -cycle in G contributes both clockwise and counterclockwise orientations. Moreover, since the entries of \beta D(G)+\gamma A(G) corresponding to the edges of this l -cycle at positions (i_{1},i_{2}) , (i_{2},i_{3}) , …, (i_{l-1},i_{l}) and (i_{l},i_{1}) are all \gamma . In any case, the total contribution of l -cycles to c_{(k,1^{n-k}),r}(\beta D(G)+\gamma A(G)) is 2|\mathscr{C}_{l}(G)|\gamma^{l}\big[\binom{n-l-1}{k-l-1}+(-1)^{l-1}\binom{n-l-1}{k-1}\big] . Contributions to c_{(k,1^{n-k}),3}(\beta D(G)+\gamma A(G)) come from three sources: \beta^{3}F_{3}(G)\binom{n-1}{k-1} from \sigma=\text{id} , \frac{(2k-n-1)\beta\gamma^{2}\mathcal{M}_{3}^{1}(G)}{k-1}\binom{n-2}{k-2} from transpositions swapping “endpoints” of edges, and the remaining term from 3 -cycles. By Claim 4.1 , we deduce the contribution of 3 -cycles is 2|\mathscr{C}_{3}(G)|\gamma^{3}\big[\binom{n-4}{k-4}+\binom{n-4}{k-1}\big] . Therefore, it is easy to obtain c_{(k,1^{n-k}),3}(\beta D(G)+\gamma A(G))=\beta^{3}F_{3}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta\gamma^{2}\mathcal{M}_{3}^{1}(G)}{k-1}\binom{n-2}{k-2}+2|\mathscr{C}_{3}(G)|\gamma^{3}\big[\binom{n-4}{k-4}-\binom{n-4}{k-1}\big] . If n\geq 5 , contributions to x^{n-4} come from five sources. The first is \sigma=\text{id} , accounting for the term \beta^{4}F_{4}(G)\binom{n-1}{k-1} . The second source is the set of transpositions swapping vertices forming an edge. In this case, by Lemma 4.1 , the value of this contribution is \frac{(2k-n-1)\beta^{2}\gamma^{2}\mathcal{M}_{4}^{1}}{k-1}\binom{n-2}{k-2} . The third source is the set of transpositions swapping vertices forming a 3 -cycle. By Lemma 2.12 , we obtain this contribution as \beta\gamma^{3}\mathcal{C}_{4}^{3}(G)\big[\binom{n-4}{k-4}-\binom{n-4}{k-1}\big] . The fourth source is 4 -cycles. By Claim 4.1 , this contribution is 2|\mathscr{C}_{4}(G)|\gamma^{4}\big[\binom{n-5}{k-5}-\binom{n-5}{k-1}\big] . The last source is 2 -matchings. By Lemma 2.12 , we have \big[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\big]\big[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\big]\gamma^{4} as the contribution from 2 -matchings. In total, we have c_{(k,1^{n-k}),4}(\beta D(G)+\gamma A(G))=\beta^{4}F_{4}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta^{2}\gamma^{2}\mathcal{M}_{4}^{1}}{k-1}\binom{n-2}{k-2}+\beta\gamma^{3}\mathcal{C}_{4}^{3}(G)\big[\binom{n-4}{k-4}-\binom{n-4}{k-1}\big]+2|\mathscr{C}_{4}(G)|\gamma^{4}\big[\binom{n-5}{k-5}-\binom{n-5}{k-1}\big]+\big[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\big]\big[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\big]\gamma^{4} . Contributions to c_{(k,1^{n-k}),5}(\beta D(G)+\gamma A(G)) come from the following sources. \beta^{5}F_{5}(G)\binom{n-1}{k-1} from \sigma=\text{id} . \frac{(2k-n-1)\beta^{3}\gamma^{2}\mathcal{M}_{5}^{1}(G)}{k-1}\binom{n-2}{k-2} from transpositions swapping “endpoints” of edges. By Claim 4.1 , we deduce the contributions of 3 -cycles and 4 -cycles are 2\beta^{2}\gamma^{3}\mathcal{C}_{5}^{3}(G)\big[\binom{n-4}{k-4}+\binom{n-4}{k-1}\big] and 2\beta\gamma^{4}\mathcal{C}_{5}^{4}(G)\big[\binom{n-5}{k-5}-\binom{n-5}{k-1}\big] , respectively. The term \beta\gamma^{4}\mathcal{M}_{5}^{2}(G)\big[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\big] represents the contribution from 2 -matchings, as given by Lemma 2.12 . Claim 4.1 directly implies that the contribution value of 5 -cycles is given by 2|\mathscr{C}_{5}(G)|\gamma^{5}\big[\binom{n-6}{k-6}-\binom{n-6}{k-1}\big] . Moreover, by Lemma 4.2 , the total contribution from all disjoint unions of one 3 -cycle and one P_{2} is expressed as \displaystyle\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}(m+3-\mathscr{T}_{j}(G))\gamma^{5}\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg] Therefore, we have c_{(k,1^{n-k}),5}(\beta D(G)+\gamma A(G))=\beta^{5}F_{5}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\beta^{3}\gamma^{2}\mathcal{M}_{5}^{1}(G)}{k-1}\binom{n-2}{k-2}+2\beta^{2}\gamma^{3}\mathcal{C}_{5}^{3}(G)\\ \big[\binom{n-4}{k-4}+\binom{n-4}{k-1}\big]+2\beta\gamma^{4}\mathcal{C}_{5}^{4}(G)\big[\binom{n-5}{k-5}-\binom{n-5}{k-1}\big]+\beta\gamma^{4}\mathcal{M}_{5}^{2}(G)\big[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\big]+2|\mathscr{C}_{5}(G)|\gamma^{5}\big[\binom{n-6}{k-6}-\binom{n-6}{k-1}\big]+\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}(m+3-\mathscr{T}_{j}(G))\gamma^{5}\big[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\big] . Based on the above arguments, we complete the proof of Theorem 4.3 . ∎ The equivalence between the hook immanantal polynomials of A(G) and \beta D(G)+\gamma A(G) is characterized as follows. Theorem 4.4 . Let \beta and \gamma be two nonzero real numbers. Let G and G^{\prime} be two regular graphs. Then the following two statements are equivalent: (i) \operatorname{Imm}_{(k,1^{n-k})}(xI-A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-A(G^{\prime})) . (ii) \operatorname{Imm}_{(k,1^{n-k})}(xI-\beta D(G)-\gamma A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-\beta D(G^{\prime})-\gamma A(G^{\prime})) . Proof. Assume (i) holds. This means the polynomials \operatorname{Imm}_{(k,1^{n-k})}(xI-A(G)) and \operatorname{Imm}_{(k,1^{n-k})}(xI-A(G^{\prime})) have the same coefficients for x^{n} and x^{n-1} . By Theorem 4.3 , we obtain |V(G_{1})|=|V(G^{\prime})| and |E(G_{1})|=|E(G^{\prime})| . This implies G and G^{\prime} are both \frac{2|E(G)|}{|V(G)|} -regular graphs (or \frac{2|E(G^{\prime})|}{|V(G^{\prime})|} -regular graphs). Since \operatorname{Imm}_{(k,1^{n-k})}(xI-A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-A(G^{\prime})) , we have \operatorname{Imm}_{(k,1^{n-k})}(xI-\gamma A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-\gamma A(G^{\prime})) . Replacing x by (x-\beta\frac{2|E(G)|}{|V(G)|}) in \operatorname{Imm}_{(k,1^{n-k})}(xI-\gamma A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-\gamma A(G^{\prime})) yields \operatorname{Imm}_{(k,1^{n-k})}(xI-\beta D(G)-\gamma A(G))=\operatorname{Imm}_{(k,1^{n-k})}(xI-\beta D(G^{\prime})-\gamma A(G^{\prime})) , showing (ii) holds. The reverse steps show (ii) implies (i) . ∎ Merris [ 30 ] proved that the immanantal polynomials of the Laplacian matrices of two regular graphs are equal if and only if the immanantal polynomials of their adjacency matrices are equal, which follows directly from Theorem 4.4 . Corollary 4.5 . (Merris, [ 30 ] ) Let G and G^{\prime} be two regular graphs. Then the following two statements are equivalent: (i) \operatorname{Imm}_{(2,1^{n-2})}(xI-A(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-A(G^{\prime})) . (ii) \operatorname{Imm}_{(2,1^{n-2})}(xI-L(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-L(G^{\prime})) . When \beta=1 and \gamma=1 , the following corollary can be obtained. Corollary 4.6 . Let G and G^{\prime} be two regular graphs. Then the following two statements are equivalent: (i) \operatorname{Imm}_{(2,1^{n-2})}(xI-A(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-A(G^{\prime})) . (ii) \operatorname{Imm}_{(2,1^{n-2})}(xI-Q(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-Q(G^{\prime})) . When 0<\beta<1 and \gamma=1-\beta , a corollary concerning the A_{\alpha} matrix can be derived. Corollary 4.7 . Let G and G^{\prime} be two regular graphs. If \alpha\notin\{0,1\} , then the following two statements are equivalent: (i) \operatorname{Imm}_{(2,1^{n-2})}(xI-A(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-A(G^{\prime})) . (ii) \operatorname{Imm}_{(2,1^{n-2})}(xI-A_{\alpha}(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-A_{\alpha}(G^{\prime})) . Corollary 4.8 . (Merris, [ 30 ] ) Let G and G^{\prime} be two regular graphs. Then the following two statements are equivalent: (i) \operatorname{Imm}_{(2,1^{n-2})}(xI-A(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-A(G^{\prime})) . (ii) \operatorname{Imm}_{(2,1^{n-2})}(xI-L(G))=\operatorname{Imm}_{(2,1^{n-2})}(xI-L(G^{\prime})) . 5. The lower bound for the multiplicity of the root \beta of immanantal polynomials of linear combination matrices of graphs In this section, we investigates the roots of the immanantal polynomials associated with linear combination matrices of graphs. First, a generalization of the Frobenius-König theorem and the Laplace expansion theorem to immanants is given. Utilizing these two theorems, we establish that the star degree of a graph serves as a lower bound for the multiplicity of the root \beta in the immanantal polynomial of its linear combination matrix. Theorem 5.1 . Let M be a square matrix of order n . If M contains a y\times z zero submatrix with y+z=n+1 , then \operatorname{Imm}_{\lambda}(M)=0 Proof. In Equation ( 1 ), we consider a term \chi_{\lambda}(\sigma)m_{1\sigma(1)}m_{2\sigma(2)}\cdots m_{n\sigma(n)} in the expansion of \operatorname{Imm}_{\lambda}(M) , where m_{ij} is the (i,j) entry of M . Assume this zero submatrix consists of y rows and z columns, denoted by sets \mathcal{Y} and \mathcal{Z} , respectively. This means for any i\in\mathcal{Y} and j\in\mathcal{Z} , we have m_{ij}=0 . Since y+z=n+1 , we have y=n-z+1 . Consider any permutation \sigma , which maps the y row indices in \mathcal{Y} to n column indices. The number of nonzero columns (i.e., columns not in \mathcal{Z} ) is n-z . By the pigeonhole principle, at least one of the column indices obtained by mapping the elements of \mathcal{Y} via \sigma must belong to \mathcal{Z} . This means there exists i_{0}\in\mathcal{Y} such that \sigma(i_{0})\in\mathcal{Z} , and then the corresponding element m_{i_{0}\sigma(i_{0})}=0 . Clearly, the term corresponding to this permutation is zero. Note that the above conclusion holds for all permutations, so we infer that all terms in the expansion of \operatorname{Imm}_{\lambda}(M) are zero, hence \operatorname{Imm}_{\lambda}(M)=0 . ∎ Definition 5.2 . Let \mathcal{R} and \mathcal{U} be two subsets of \{1,2,\dots,n\} , with complements \mathcal{R}^{\prime}=\{1,\dots,n\}\setminus\mathcal{R} and \mathcal{U}^{\prime}=\{1,\dots,n\}\setminus\mathcal{U} . The submatrix M[\mathcal{R},\mathcal{U}] (respectively M[\mathcal{R}^{\prime},\mathcal{U}^{\prime}] ) is formed by selecting from matrix M rows with indices in set \mathcal{R} (respectively \mathcal{R}^{\prime} ) and columns with indices in set \mathcal{U} (respectively \mathcal{U}^{\prime} ). Theorem 5.3 . Let M=[m_{ij}] be an n\times n matrix, and \mu\vdash r , \nu\vdash n-r . Suppose \mathcal{R} , \mathcal{R}^{\prime} , \mathcal{U} , \mathcal{U}^{\prime} , M[\mathcal{R},\mathcal{U}] and M[\mathcal{R}^{\prime},\mathcal{U}^{\prime}] are as defined in Definition 5.2 . Then \displaystyle\operatorname{Imm}_{\lambda}(M) \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\begin{subarray}{c}\mu\vdash r\\ \nu\vdash n-r\end{subarray}}c_{\mu,\nu}^{\lambda}d_{\mu}(M[\mathcal{R},\mathcal{U}])d_{\nu}(M[\mathcal{R}^{\prime},\mathcal{U}^{\prime}]), where c_{\mu,\nu}^{\lambda} are Littlewood–Richardson coefficients. Proof. Fix an r -element row subset \mathcal{R}\subseteq\{1,2,\dots,n\} , whose complement \mathcal{R}^{\prime}=\{1,\dots,n\}\setminus\mathcal{R} contains n-r elements. Any permutation \sigma\in\mathcal{S}_{n} can be decomposed into two independent bijections: \displaystyle\sigma_{1}=\sigma|_{\mathcal{R}}:\mathcal{R}\to\mathcal{U},\quad\text{where }\mathcal{U}\text{ is an }r\text{-element column subset,} \displaystyle\sigma_{2}=\sigma|_{\mathcal{U}^{\prime}}:\mathcal{R}^{\prime}\to\mathcal{U}^{\prime},\quad\text{where}~\mathcal{U}^{\prime}=\{1,\dots,n\}\setminus\mathcal{R}\text{ contains}~n-r~\text{elements}. Let S(\mathcal{R},\mathcal{U}) and S(\mathcal{R}^{\prime},\mathcal{U}^{\prime}) denote the sets consisting of all such \sigma_{1} and \sigma_{2} , respectively. This implies (11) \displaystyle\sigma=\sigma_{1}\oplus\sigma_{2}, and all permutations can be partitioned according to the column subset \mathcal{U} into disjoint unions: (12) \displaystyle\mathcal{S}_{n}=\bigsqcup_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\mathcal{S}(\mathcal{R},\mathcal{U})\times\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime}). From Equations ( 11 ) and ( 12 ), we have (13) \displaystyle\operatorname{Imm}_{\lambda}(M) \displaystyle= \displaystyle\sum_{\sigma\in\mathcal{S}_{n}}\chi_{\lambda}(\sigma)\prod_{i=1}^{n}m_{i\sigma(i)} \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\sigma_{1}\in\mathcal{S}(\mathcal{R},\mathcal{U})}\sum_{\sigma_{2}\in\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime})}\chi(\sigma_{1}\oplus\sigma_{2})\prod_{i\in\mathcal{R}}m_{i\sigma_{1}(i)}\prod_{i\in\mathcal{R}^{\prime}}m_{i\sigma_{2}(i)}. According to the definition of immanant, we derive \displaystyle\operatorname{Imm}_{\mu}(M[\mathcal{R},\mathcal{U}])=\sum_{\sigma_{1}\in\mathcal{S}(\mathcal{R},\mathcal{U})}\chi_{\mu}(\sigma_{1})\prod_{i\in\mathcal{R}}m_{i\sigma_{1}(i)} and \displaystyle\operatorname{Imm}_{\nu}(M[\mathcal{R}^{\prime},\mathcal{U}^{\prime}])=\sum_{\sigma_{2}\in\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime})}\chi_{\nu}(\sigma_{2})\prod_{i\in\mathcal{R}^{\prime}}m_{i\sigma_{2}(i)}. From Lemma 2.10 and Equation ( 13 ), we obtain \displaystyle\operatorname{Imm}_{\lambda}(M) \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\sigma_{1}\in\mathcal{S}(\mathcal{R},\mathcal{U})}\sum_{\sigma_{2}\in\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime})}\chi(\sigma_{1}\oplus\sigma_{2})\prod_{i\in\mathcal{R}}m_{i\sigma_{1}(i)}\prod_{i\in\mathcal{R}^{\prime}}m_{i\sigma_{2}(i)} \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\sigma_{1}\in\mathcal{S}(\mathcal{R},\mathcal{U})}\sum_{\sigma_{2}\in\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime})}\sum_{\begin{subarray}{c}\mu\vdash r\\ \nu\vdash n-r\end{subarray}}c_{\mu,\nu}^{\lambda}\;\chi_{\mu}(\sigma_{1})\,\chi_{\nu}(\sigma_{2})\prod_{i\in\mathcal{R}}m_{i\sigma_{1}(i)}\prod_{i\in\mathcal{R}^{\prime}}m_{i\sigma_{2}(i)} \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\begin{subarray}{c}\mu\vdash r\\ \nu\vdash n-r\end{subarray}}c_{\mu,\nu}^{\lambda}\Bigg\{\sum_{\mu\in\mathcal{S}(\mathcal{R},\mathcal{U})}\chi_{\mu}(\sigma_{1})\prod_{i\in\mathcal{R}}m_{i\sigma_{1}(i)}\Bigg\}\Bigg\{\sum_{\nu\in\mathcal{S}(\mathcal{R}^{\prime},\mathcal{U}^{\prime})}\chi_{\nu}(\sigma_{2})\prod_{i\in\mathcal{R}^{\prime}}m_{i\sigma_{2}(i)}\Bigg\} \displaystyle= \displaystyle\sum_{\begin{subarray}{c}\mathcal{U}\subseteq\{1,\dots,n\}\\ |\mathcal{U}|=r\end{subarray}}\sum_{\begin{subarray}{c}\mu\vdash r\\ \nu\vdash n-r\end{subarray}}c_{\mu,\nu}^{\lambda}\operatorname{Imm}_{\mu}(M[\mathcal{R},\mathcal{U}])\operatorname{Imm}_{\nu}(M[\mathcal{R}^{\prime},\mathcal{U}^{\prime}]). The proof is complete. ∎ We state the special case of the theorem for r=1 as follows, to be used in later proofs. Corollary 5.4 . Let M=[m_{ij}] be an n\times n matrix. Then \displaystyle\operatorname{Imm}_{\lambda}(M)=\sum\limits_{j=1}^{n}c_{(1),\nu}^{\lambda}m_{ij}\operatorname{Imm}_{\nu}(M[\{1,\ldots,n\}\setminus\{i\},\{1,\ldots,n\}\setminus\{j\}]), where \nu is the partition obtained by removing a rim hook of size 1 from the Young diagram corresponding to \lambda , and c_{(1),\nu}^{\lambda} are Littlewood–Richardson coefficients. From Equality ( 2 ) and Lemma 2.4 , we can deduce the following conclusion. Suppose M is an n\times n matrix, and \operatorname{Imm}_{\lambda}(xI-M) is defined as in Equality ( 2 ). If c_{\lambda,n}(M)=c_{\lambda,n-1}(M)=\cdots=c_{\lambda,n-(p-1)}(M)=0 , then 0 is a root of \operatorname{Imm}_{\lambda}(xI-M) with multiplicity at least p . Suppose M=\beta D(G)+\gamma A(G)-\beta I , and 0 is a root of \operatorname{Imm}_{\lambda}(xI-M) with multiplicity at least p . Then \displaystyle\operatorname{Imm}_{\lambda}(xI-\beta D(G)-\gamma A(G)) \displaystyle= \displaystyle\operatorname{Imm}_{\lambda}(xI-(M+\beta I))=\operatorname{Imm}_{\lambda}((x-1)I-M) \displaystyle= \displaystyle c_{\lambda,0}(M)(x-1)^{n}-c_{\lambda,1}(M)(x-1)^{n-1}+c_{\lambda,2}(M)(x-1)^{n-2}-\cdots+(-1)^{n}c_{\lambda,n}(M). This means that \beta is a root of \operatorname{Imm}_{\lambda}(xI-\beta D(G)-\gamma A(G)) with multiplicity at least p . Theorem 5.5 . Let G be a connected graph with n vertices. The multiplicity of the root \beta in \operatorname{Imm}_{\lambda}(xI-\beta D(G)-\gamma A(G)) is greater than or equal to the star degree of G . Proof. Depending on the value of p>0 , we consider two cases. Case 1. Suppose p=0 . Note that the multiplicity of the root \beta in \operatorname{Imm}_{\lambda}(xI-\beta D(G)-\gamma A(G)) is greater than or equal to zero, so we deduce that Theorem 5.5 holds. Case 2. Suppose p\geq 1 . This means the graph contains s star centers ( s\geq 1 ), each with \omega_{1},\ldots,\omega_{s} pendant vertices ( \omega_{i}\geq 1 ), and \sum\limits_{i=1}^{s}(\omega_{i}-1)=p . We can assign labels to vertices as follows: denote the s center vertices as v_{n},v_{n-1},\ldots,v_{n-s+1} , denote the \omega_{1} pendant vertices adjacent to v_{n} as v_{1},\ldots,v_{\omega_{1}} , denote the \omega_{2} vertices adjacent to v_{n-1} as v_{\omega_{1}+1},\ldots,v_{\omega_{1}+\omega_{2}} , and so on; the remaining n-s-\sum\limits_{i=1}^{s}\omega_{i} non-pendant vertices can be arbitrarily labeled as v_{\omega_{1}+\cdots+\omega_{r}+1},\ldots,v_{n-s} . Using this labeling scheme, we can assume the matrix \beta D(G)+\gamma A(G) has the following form. \footnotesize\left[\begin{array}[]{ccc|ccc|c|ccc|c|c|c|c|c}\beta&\cdots&0&&&&&&&&&&&&\gamma\\ 0&\ddots&0&&0&&0&&0&&0&0&0&0&\vdots\\ 0&\cdots&\beta&&&&&&&&&&&&\gamma\\ \hline\cr&&&\beta&\cdots&0&&&&&&&&\gamma&\\ &0&&&\ddots&&0&&0&&0&0&0&\vdots&0\\ &&&0&\cdots&\beta&&&&&&&&\gamma&\\ \hline\cr&\vdots&&&\vdots&&\ddots&&\vdots&&\vdots&&{\scriptsize\rotatebox{90.0}{$\ddots$}}&&\\ \hline\cr&&&&&&&\beta&&0&&\gamma&&&\\ &0&&&0&&\cdots&&\ddots&&0&\vdots&0&0&0\\ &&&&&&&0&&\beta&&\gamma&&&\\ \hline\cr&0&&&0&&0&&0&&*&*&*&*&*\\ \hline\cr&0&&&0&&0&\gamma&\cdots&\gamma&*&\beta d(v_{n-s-1})&&&*\\ \hline\cr&0&&&0&&{\scriptsize\rotatebox{90.0}{$\ddots$}}&&0&&*&&\ddots&&\\ \hline\cr&0&&\gamma&\cdots&\gamma&\cdots&&0&&*&&&\beta d(v_{n-1})&\\ \hline\cr\gamma&\cdots&\gamma&&0&&0&&0&&*&*&&&\beta d(v_{n})\\ \end{array}\right]_{n\times n} Using this notation, the matrix \beta D(G)+\gamma A(G) satisfies d(v_{j})\geq 2 for j=\omega_{1}+\omega_{2}+\cdots+\omega_{s}+1,\ldots,n . Our goal is to prove that the multiplicity of the root \beta in the polynomial \operatorname{Imm}_{\lambda}(\beta D(G)+\gamma A(G)-xI) is at least p , which is equivalent to proving that the multiplicity of the root 0 in the polynomial \operatorname{Imm}_{\lambda}(\beta D(G)+\gamma A(G)-\beta I-xI) is also at least p . Now consider the matrix \beta D(G)+\gamma A(G)-\beta I , which has the following block structure. \footnotesize\left[\begin{array}[]{ccc|ccc|c|ccc|c|c|c|c|c}&&&&&&&&&&&&&&\gamma\\ &0&&&0&&0&&0&&0&0&0&0&\vdots\\ &&&&&&&&&&&&&&\gamma\\ \hline\cr&&&&&&&&&&&&&\gamma&\\ &0&&&0&&0&&0&&0&0&0&\vdots&0\\ &&&&&&&&&&&&&\gamma&\\ \hline\cr&\vdots&&&\vdots&&\ddots&&\vdots&&\vdots&&{\scriptsize\rotatebox{90.0}{$\ddots$}}&&\\ \hline\cr&&&&&&&&&&&\gamma&&&\\ &0&&&0&&\cdots&&0&&0&\vdots&0&0&0\\ &&&&&&&&&&&\gamma&&&\\ \hline\cr&0&&&0&&0&&0&&*&*&*&*&*\\ \hline\cr&0&&&0&&0&\gamma&\cdots&\gamma&*&\beta(d(v_{n-r-1})-1)&&&*\\ \hline\cr&0&&&0&&{\scriptsize\rotatebox{90.0}{$\ddots$}}&&0&&*&&\ddots&&\\ \hline\cr&0&&\gamma&\cdots&\gamma&\cdots&&0&&*&&&\beta(d(v_{n-1})-1)&\\ \hline\cr\gamma&\cdots&\gamma&&0&&0&&0&&*&*&&&\beta(d(v_{n})-1)\\ \end{array}\right]_{n\times n} We aim to prove that 0 is a root of \operatorname{Imm}_{\lambda}(\beta D(G)+\gamma A(G)-\beta I-xI) with multiplicity at least p . Given \omega_{1}+\cdots+\omega_{s}=\omega and \sum\limits_{i=1}^{s}(\omega_{i}-1)=p . This implies \omega-s=p . Now consider principal submatrices of order n-(p-1) . Each such principal submatrix contains a [\omega-(p-1)]\times[(n-s)-(p-1)] zero submatrix in its upper left corner. Note that (\omega-p+1)+(n-s-p+1)=n-p+2 . By Theorem 5.1 , we infer that the immanant of every principal submatrix of order n-(p-1) of \beta D(G)+\gamma A(G)-\beta I equals 0 . Indeed, each n-(p-1) submatrix contains a [\omega-(p-1)]\times[(n-s)-(p-1)] zero submatrix in its upper left corner. This indicates all these submatrices satisfy the conditions of Theorem 5.1 . By Corollary 5.11 , the immanant of each z submatrix, where n-(p-1)\leq z\leq n , equals 0 . In particular, all principal submatrices of order z in this range have zero immanant. Applying Equation ( 2 ) and its conclusion, we deduce that \beta is a root of \operatorname{Imm}_{\lambda}(\beta D(G)+\gamma A(G)-xI) with multiplicity at least p . ∎ For \beta=1 and \gamma=-1 , the above results directly yield the following conclusion. Corollary 5.6 . Let G be a connected graph with n vertices. The multiplicity of the root 1 in \operatorname{Imm}_{\lambda}(xI-L(G)) is greater than or equal to the star degree of G . In the cases \lambda=(1^{n}) and \lambda=(n) , the star degree of G provides a lower bound for the multiplicity of the root 1 of the characteristic polynomial and the permanental polynomial of G . This result was derived by Faria in [ 15 ] . Corollary 5.7 . (Faria, [ 15 ] ) Let G be a connected graph with n vertices. The multiplicity of the root 1 in {\rm det}(xI-L(G)) is greater than or equal to the star degree of G . Corollary 5.8 . (Faria, [ 16 ] ) Let G be a connected graph with n vertices. The multiplicity of the root 1 in {\rm per}(xI-L(G)) is greater than or equal to the star degree of G . Merris [ 30 ] further posed an open problem: whether the star degree of G is always a lower bound for the multiplicity of the root 1 in d_{(2,1^{n-2})}(xI-L(G)) ? Wu et al. [ 40 ] proved that the multiplicity of the root 1 of \operatorname{Imm}_{(2,1^{n-2})}(xI-L(G)) is at least the star degree of G , resolving this open problem. This result is contained in Theorem 5.5 . Corollary 5.9 . (Wu et al., [ 40 ] ) Let G be a connected graph. The multiplicity of the root 1 in \operatorname{Imm}_{(2,1^{n-2})}(xI-L(G)) is greater than or equal to the star degree of G . For \beta=1 and \gamma=1 , the above results directly yield the following conclusion. Corollary 5.10 . Let G be a connected graph with n vertices. The multiplicity of the root 1 of \operatorname{Imm}_{\lambda}(xI-Q(G)) is at least the star degree of G . For 0<\beta<1 and \gamma=1-\beta , the above results directly yield the following conclusion. Corollary 5.11 . Let G be a connected graph with n vertices. If \alpha\notin\{0,1\} , then the multiplicity of the root \alpha of \operatorname{Imm}_{\lambda}(xI-A_{\alpha}(G)) is at least the star degree of G . 6. Further discussion on theorem 4.3 In this section, we provide an in-depth discussion of Theorem 4.3 . Using Theorem 4.3 , we can obtain formulas for the first six coefficients of the hook immanantal polynomials of the Laplacian matrix, the signless Laplacian matrix, the adjacency matrix and the A_{\alpha} matrix of a graph. When \beta=1 and \gamma=-1 , the first six coefficients of the hook immanantal polynomial of L(G) can be obtained. Corollary 6.1 . Let G be a graph with n vertices and m edges, and (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle\operatorname{Imm}_{(k,1^{n-k})}(xI-L(G))=\sum_{r=0}^{n}(-1)^{r}c_{(k,1^{n-k}),r}(L(G))x^{n-r}. Then \displaystyle c_{(k,1^{n-k}),0}(L(G)) \displaystyle= \displaystyle\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),1}(L(G)) \displaystyle= \displaystyle F_{1}(G)\binom{n-1}{k-1}=2m\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),2}(L(G)) \displaystyle= \displaystyle F_{2}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)m}{k-1}\binom{n-2}{k-2}\quad(n\geq 3), \displaystyle c_{(k,1^{n-k}),3}(L(G)) \displaystyle= \displaystyle F_{3}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{M}_{3}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle-2|\mathscr{C}_{3}(G)|\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]\quad(n\geq 4), \displaystyle c_{(k,1^{n-k}),4}(L(G)) \displaystyle= \displaystyle F_{4}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{M}_{4}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle-\mathcal{C}_{4}^{3}(G)\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]+2|\mathscr{C}_{4}(G)|\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\bigg[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\bigg]\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]\quad(n\geq 5), and \displaystyle c_{(k,1^{n-k}),5}(L(G)) \displaystyle= \displaystyle F_{5}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{M}_{5}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle-2\mathcal{C}_{5}^{3}(G)\bigg[\binom{n-4}{k-4}+\binom{n-4}{k-1}\bigg]+2\mathcal{C}_{5}^{4}(G)\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\mathcal{M}_{5}^{2}(G)\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]-2|\mathscr{C}_{5}(G)|\bigg[\binom{n-6}{k-6}-\binom{n-6}{k-1}\bigg] \displaystyle-\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}2(m+3-\mathscr{T}_{j}(G))\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg]\quad(n\geq 6). Corollary 6.1 directly yields the four coefficients of the second immanantal polynomials of graphs introduced by Merris [ 29 ] . Corollary 6.2 . (Merris, [ 29 ] ) Let G be a graph with n vertices and m edges. Denote \displaystyle\operatorname{Imm}_{(2,1^{n-2})}(xI-L(G))=\sum_{r=0}^{n}(-1)^{r}c_{2,r}(L(G))x^{n-r}. Then \displaystyle c_{(2,1^{n-2}),0}(L(G)) \displaystyle= \displaystyle n-1, \displaystyle c_{(2,1^{n-2}),1}(L(G)) \displaystyle= \displaystyle(n-1)F_{1}(G)=2m(n-1), \displaystyle c_{(2,1^{n-2}),2}(L(G)) \displaystyle= \displaystyle(n-1)F_{2}(G)-m(n-3)\quad(n\geq 3), and \displaystyle c_{(2,1^{n-2}),3}(L(G)) \displaystyle= \displaystyle(n-1)F_{3}(G)-(n-3)\mathcal{M}_{3}^{1}(G)-2(n-4)|\mathscr{C}_{3}(G)|\quad(n\geq 4). Under the conditions \beta=1 and \gamma=1 , the first six coefficients of the hook immanantal polynomial of Q(G) can be derived. Corollary 6.3 . Let G be a graph with n vertices and m edges, and let (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle\operatorname{Imm}_{(k,1^{n-k})}(xI-Q(G))=\sum_{r=0}^{n}(-1)^{r}c_{k(k,1^{n-k}),r}(Q(G))x^{n-r}. Then \displaystyle c_{(k,1^{n-k}),0}(Q(G)) \displaystyle= \displaystyle\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),1}(Q(G)) \displaystyle= \displaystyle F_{1}(G)\binom{n-1}{k-1}=2m\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),2}(G) \displaystyle= \displaystyle F_{2}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)m}{k-1}\binom{n-2}{k-2}\quad(n\geq 3), \displaystyle c_{(k,1^{n-k}),3}(Q(G)) \displaystyle= \displaystyle F_{3}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{E}_{3}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2|\mathscr{C}_{3}(G)|\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]\quad(n\geq 4), \displaystyle c_{(k,1^{n-k}),4}(Q(G)) \displaystyle= \displaystyle F_{4}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{E}_{4}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+\mathcal{C}_{4}^{3}(G)\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]+2|\mathscr{C}_{4}(G)|\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\bigg[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\bigg]\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]\quad(n\geq 5), and \displaystyle c_{(k,1^{n-k}),5}(Q(G)) \displaystyle= \displaystyle F_{5}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\mathcal{E}_{5}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2\mathcal{C}_{5}^{3}(G)\bigg[\binom{n-4}{k-4}+\binom{n-4}{k-1}\bigg]+2\mathcal{C}_{5}^{4}(G)\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\mathcal{M}_{5}^{2}(G)\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]+2|\mathscr{C}_{5}(G)|\bigg[\binom{n-6}{k-6}-\binom{n-6}{k-1}\bigg] \displaystyle+\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}2(m+3-\mathscr{T}_{j}(G))\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg]\quad(n\geq 6). Setting \beta=0 and \gamma=1 gives the first six coefficients of the hook immanantal polynomial of A(G) . Corollary 6.4 . Let G be a graph with n vertices and m edges, and (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle\operatorname{Imm}_{(k,1^{n-k})}(xI-A(G))=\sum_{r=0}^{n}(-1)^{r}c_{(k,1^{n-k}),r}(A(G))x^{n-r}. Then \displaystyle c_{(k,1^{n-k}),0}(A(G)) \displaystyle= \displaystyle\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),1}(A(G)) \displaystyle= \displaystyle 0, \displaystyle c_{(k,1^{n-k}),2}(A(G)) \displaystyle= \displaystyle\frac{(2k-n-1)m}{k-1}\binom{n-2}{k-2}\quad(n\geq 3), \displaystyle c_{(k,1^{n-k}),3}(A(G)) \displaystyle= \displaystyle 2|\mathscr{C}_{3}(G)|\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]\quad(n\geq 4), \displaystyle c_{(k,1^{n-k}),4}(A(G)) \displaystyle= \displaystyle\bigg[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\bigg]\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg] \displaystyle+2|\mathscr{C}_{4}(G)|\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg]\quad(n\geq 5), and \displaystyle c_{(k,1^{n-k}),5}(A(G)) \displaystyle= \displaystyle\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}2(m+3-\mathscr{T}_{j}(G))\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg] \displaystyle+2|\mathscr{C}_{5}(G)|\bigg[\binom{n-6}{k-6}-\binom{n-6}{k-1}\bigg]\quad(n\geq 6). Using Corollary 6.4 , we can derive the first six coefficients of the permanent polynomial of G , which were proposed by Liu and Zhang [ 23 ] . Corollary 6.5 . ( Liu and Zhang, [ 23 ] ) Let G be a graph with n vertices and m edges, and (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle{\rm per}(xI-A(G))=\sum_{r=0}^{n}(-1)^{r}c_{(n),r}(A(G))x^{n-r}. Then \displaystyle c_{(n),0}(A(G)) \displaystyle= \displaystyle 1, \displaystyle c_{(n),1}(A(G)) \displaystyle= \displaystyle 0, \displaystyle c_{(n),2}(A(G)) \displaystyle= \displaystyle m, \displaystyle c_{(n),3}(A(G)) \displaystyle= \displaystyle 2|\mathscr{C}_{3}(G)|, \displaystyle c_{(n),4}(A(G)) \displaystyle= \displaystyle\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}+2|\mathscr{C}_{4}(G)|. Under the conditions 0\leq\beta\leq 1 and \gamma=1-\beta , the first six coefficients of the hook immanantal polynomial of A_{\alpha}(G) can be derived. Corollary 6.6 . Let G be a graph with n vertices and m edges, and let (d(v_{1}),d(v_{2}),\ldots,d(v_{n})) denote the degree sequence of G . Denote \displaystyle\operatorname{Imm}_{(k,1^{n-k})}(xI-A_{\alpha}(G))=\sum_{r=0}^{n}(-1)^{r}c_{(k,1^{n-k}),r}(A_{\alpha}(G))x^{n-r}. Then \displaystyle c_{(k,1^{n-k}),0}(A_{\alpha}(G)) \displaystyle= \displaystyle\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),1}(A_{\alpha}(G)) \displaystyle= \displaystyle 2m\alpha\binom{n-1}{k-1}, \displaystyle c_{(k,1^{n-k}),2}(A_{\alpha}(G)) \displaystyle= \displaystyle\alpha^{2}F_{2}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)m(1-\alpha)^{2}}{k-1}\binom{n-2}{k-2}\quad(n\geq 3), \displaystyle c_{(k,1^{n-k}),3}(A_{\alpha}(G)) \displaystyle= \displaystyle\alpha^{3}F_{3}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\alpha(1-\alpha)^{2}\mathcal{M}_{3}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2|\mathscr{C}_{3}(G)|(1-\alpha)^{3}\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]\quad(n\geq 4), \displaystyle c_{(k,1^{n-k}),4}(A_{\alpha}(G)) \displaystyle= \displaystyle\alpha^{4}F_{4}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\alpha^{2}(1-\alpha)^{2}\mathcal{M}_{4}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+\alpha(1-\alpha)^{3}\mathcal{C}_{4}^{3}(G)\bigg[\binom{n-4}{k-4}-\binom{n-4}{k-1}\bigg]+2|\mathscr{C}_{4}(G)|(1-\alpha)^{4}\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\bigg[\binom{m}{2}-\sum\limits_{i=1}^{n}\binom{d(v_{i})}{2}\bigg]\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg](1-\alpha)^{4}\quad(n\geq 5), and \displaystyle c_{(k,1^{n-k}),5}(A_{\alpha}(G)) \displaystyle= \displaystyle\alpha^{5}F_{5}(G)\binom{n-1}{k-1}+\frac{(2k-n-1)\alpha^{3}\gamma^{2}\mathcal{M}_{5}^{1}(G)}{k-1}\binom{n-2}{k-2} \displaystyle+2\alpha^{2}(1-\alpha)^{3}\mathcal{C}_{5}^{3}(G)\bigg[\binom{n-4}{k-4}+\binom{n-4}{k-1}\bigg]+2\alpha(1-\alpha)^{4}\mathcal{C}_{5}^{4}(G)\bigg[\binom{n-5}{k-5}-\binom{n-5}{k-1}\bigg] \displaystyle+\alpha(1-\alpha)^{4}\mathcal{M}_{5}^{2}(G)\bigg[\binom{n-5}{k-5}-2\binom{n-5}{k-3}+\binom{n-5}{k-1}\bigg]+2|\mathscr{C}_{5}(G)|(1-\alpha)^{5}\bigg[\binom{n-6}{k-6}-\binom{n-6}{k-1}\bigg] \displaystyle+\sum\limits_{j=1}^{|\mathscr{C}_{3}(G)|}2(m+3-\mathscr{T}_{j}(G))(1-\alpha)^{5}\bigg[\binom{n-6}{k-6}+\binom{n-6}{k-3}-\binom{n-6}{k-4}-\binom{n-6}{k-1}\bigg]\quad(n\geq 6). 7. Conclusion This paper mainly studies the immanant polynomials of the linear combination matrix \beta D(G)+\gamma A(G) of a graph. We establish upper and lower bounds for the coefficients of the immanantal polynomials of the linear combination matrices of graphs. These bounds not only extend the known inequalities of Chan and Lam from trees and bipartite graphs to general graphs, but also cover special cases such as the Laplacian matrix, the signless Laplacian matrix, and the A_{\alpha} matrix. By precisely characterizing the first six coefficients of the hook immanantal polynomial, we derive a necessary and sufficient condition for the equality of the hook immanantal polynomials of linear combination matrices of two regular graphs. Moreover, necessary and sufficient conditions for the equality of the hook immanantal polynomials of the Laplacian matrix, the signless Laplacian matrix, and the A_{\alpha} matrix of regular graphs are obtained. In addition, we provide explicit expressions for specific cases, including the coefficients of Merris’s second immanantal polynomial and the coefficients of Liu and Zhang’s permanent polynomial. Through extending the matrix versions of the Frobenius–König theorem and the Laplace expansion theorem to immanant functions, we show that the star degree of a graph equals the multiplicity of the root \beta in the immanantal polynomial of its linear combination matrix. This conclusion subsumes the result of Wu et al. on the root multiplicity of the second immanant of the Laplacian matrix as a special case. Based on general theoretical principles, this paper systematically deduces many previously known important conclusions, achieving the generalization and unification of multiple classical results. This not only verifies the validity of existing findings, but also helps people understand the rich content and inherent patterns of the generalized matrix function immanant in graph theory from a unified perspective. Data Availability No data were used to support this study. Disclosure statement The authors declare that they have no conflicts of interest. Funding This research is supported by NSFC (No. 12261071) and NSF of Qinghai Province (No. 2025-ZJ-902T).