几乎正则完全二部图的永久和

The Permanent Sum of Almost Regular Complete Bipartite Graph

摘要: 本文针对无向简单图G，探讨了其邻接矩阵A (G)与积和多项式之间的关系。具体而言，图G的积和多项式被定义为$p\left(G,x\right)=\text{per}\left(x1-A\left(G\right)\right)$ ，其中I代表单位矩阵。在此基础上，图G的永久和被定义为积和多项式π(G,x)的系数绝对值之和。本文研究重点探讨了完全二部图的永久和计算公式，并进一步刻画了部分完全正则二部图在删边操作后其子图的永久和计算方法。此外，给出了有向树与无向树的积和谱的关系。

Abstract: This paper focuses on the relationship between the adjacency matrix A(G) and the permanental polynomial for an undirected simple graph G. Specifically, the permanental polynomial of graph G is defined as $p\left(G,x\right)=\text{per}\left(x1-A\left(G\right)\right)$ , where I denotes the identity matrix. Based on this, the permanent sum of graph G is defined as the sum of the absolute values of the coefficients of the permanental polynomial π (G, x). This study primarily investigates the calculation formula for the permanent sum of complete bipartite graphs and further characterizes the calculation methods for the permanent sum of subgraphs obtained by edge deletion in some complete regular bipartite graphs. In addition, the relationship between the skew spectrum of directed trees and the spectrum of undirected trees is provided.

1. 引言

在本文中我们考虑的图是无向、简单图。令$G=\left(V,E\right)$ 是一个顶点集为$V(G)$ ，边集为$E(G)$ 的图。如果$G=\left[g_{ij}\right]$ 是$n\times n$ 矩阵，其中$i,j\in \{1,2,\mathrm{...},n\},$ 则矩阵$\text{G}$ 的积和式定义如下：

$\text{per}\left(G\right)={\displaystyle \sum }_{\sigma }{\displaystyle \prod }_{i=1}^n{g}_{i\sigma \left(i\right)}$

其中和式取遍$\left\{1,2,\dots ,\text{n}\right\}$ 中的所有置换$\sigma$ ，Valiant [1]已经证明了即使限定在$\left(0,1\right)$ -矩阵上，积和式的计算也是$\#p$ -完全的。

令$A\left(G\right)$ 是图$\text{G}$ 的$n$ 阶邻接矩阵，并且$I$ 是单位矩阵。图$\text{G}$ 的积和多项式定义为：

$\pi \left(G,x\right)=\text{per}\left(xI-A\left(G\right)\right)={\displaystyle \sum }_{k=0}^n{b}_k\left(G\right)x^{n-k},$

其中$b_0\left(G\right)=1,b_k\left(G\right)$ 表示多项式$\pi \left(G,x\right)$ 的系数。

Sachs子图是每一个分支是孤立边或者不交圈的图。Kasum等[2]和Merris等[3]利用Sachs子图给出了图$\text{G}$ 的积和多项式系数的Sachs型公式：

$b_k\left(G\right)={\left(-1\right)}^k{\displaystyle \sum }_{H\in S_k\left(G\right)}{2}^{c\left(H\right)},1\le k\le n,$

其中$S_k\left(G\right)$ 表示图$\text{G}$ 中所有$k$ 阶Sachs子图的集合，并且$c\left(H\right)$ 表示$H$ 中圈的数目。Wu和Lai [4]给出了永久和的定义如下。

令$\text{G}$ 是一个$n$ 阶图。图$\text{G}$ 的永久和，记为$PS\left(G\right)$ ，即：

$PS\left(G\right)={\displaystyle \sum }_{k=0}^n\left|b_k\left(G\right)\right|=1+{\displaystyle \sum }_{k=1}^n{\displaystyle \sum }_{H\in S_k\left(G\right)}{2}^{C\left(H\right)},$

是$\pi \left(G,x\right)$ 的所有系数的绝对值求和。

Wu和So [5]发现

$\begin{array}{c}{\left(-1\right)}^{n}PS\left(G\right)={\left(-1\right)}^n+{\left(-1\right)}^n{\displaystyle \sum }_{k=1}^n{\displaystyle \sum }_{H\in S_k\left(G\right)}{2}^{c\left(H\right)}\\ ={\left(-1\right)}^n+{\displaystyle \sum }_{k=1}^n{b}_k\left(G\right){\left(-1\right)}^{n-k}\\ =\pi \left(G,-1\right)\\ =\text{per}\left(-I-A\left(G\right)\right)\end{array}$

因此，他们得到图的永久和的另一个表达式：

$PS\left(G\right)=\text{per}\left(I+A\left(G\right)\right).$

并证明了永久和的计算是#p-完全的。此外，还证明了单圈图永久和的第二大和第二小及其相应的极图。

1.1. 图的永久和的研究进展

积和多项式作为积和式的衍生物，是图的一个组合不变量，涉及信息科学、网络科学、统计物理和结构化学，是图论研究的一个重要工具，在数学和化学中分别由Kasum等[2]和Merris等[3]独立提出。积和式及相关多项式在化学图论中主要用于描述分子结构和化学反应的性质，例如凯库勒结构计数，分子图的拓扑指标，化学反应的路径分析等；量子计算中的应用，如玻色子采样，量子态的描述，量子算法的设计等；统计物理中积和式与晶格模型的配分函数相关，用于研究相变和临界现象。在概率与随机矩阵方面积和式用于计算随机矩阵的期望值，在随机图论和随机网络的研究中具有重要意义。由于积和式计算的困难性，有关积和式的问题一直受到国际数学家的关注。

永久和是近年来提出的新概念。研究表明图的永久和在化学分子的物理、化学性质中表现非常活跃。仝辉[6]首次研究图的永久和。中科院院士谢素原等[7]合成了富勒烯$C_{50}\left(D_{5h}\right)$ 后，仝辉计算了$C_{50}$ 中的所有271富勒烯，在他的研究中，他发现$C_{50}\left(D_{5h}\right)$ 的永久和在$C_{50}$ 中的271个富勒烯中达到最小值，并且他还指出了永久和可能与分子图的稳定性密切相关。图的永久和在数学中也有重要的研究价值，永久和是一个关于图结构的计数指标，枚举图的所有Sachs子图的数目。永久和作为一个新的拓扑指标，近来被广泛的研究，并取得一些重要的结果[8]。一个图的永久和可以由以下方法计算：

(i) 令$\text{G}$ 和$H$ 是两个图。则

$PS\left(G \cup H\right) = PS\left(G\right)PS\left(H\right).$

(ii) 令$uv$ 是图$\text{G}$ 的一条边，且$C\left(uv\right)$ 是包含边$uv$ 的圈的集合。

$PS\left(G\right) = PS\left(G - uv\right)+ PS\left(G - v - u\right) + 2{\displaystyle \sum _{C\in C\left(uv\right)}PS\left(G-V\left(C\right)\right).}$

(iii) 令$v$ 是图$\text{G}$ 的一个顶点，$N_G\left(v\right)$ 是顶点$v$ 的领集，且$C\left(v\right)$ 是包含顶点$v$ 的圈的集合。则

$PS\left(G\right) = PS\left(G - v\right) + {\displaystyle \sum _{u\in N_G\left(v\right)}PS\left(G - v - u\right) } + 2{\displaystyle \sum _{C\in C\left(v\right)}PS\left(G-V \left(C\right)\right)}.$

吴廷增和吕华众[9]证明了准树的永久和的上界和下界以及对应的极图。李书超和魏薇在[10]中研究了八角形链的永久和的上界和下界以及对应的极图，得到螺旋型八角链的永久和最小，而锯齿型八角链的永久和最大的结论。吴廷增，任胜章和Das [11]证明了螺旋六边形链的的上界和下界以及对应的极图，此外，还证明了二部图永久和的下界以及对应的极图。吴廷增和So [12]在中计算了边数较少的图的永久和，边数较多的图的永久和的显式表达式，研究了在相同大小的所有图中，哪些图达到了永久和的极值。李巍等[13]中研究了六角链的永久和的极值，证明了线型六角链的永久和的值最小，而“之”字型六角链的永久和的值最大。吴廷增和赖虹建[14]给出了永久和的概念以及基本性质，并给出了单圈图永久和的Sachs型公式，即

$PS\left(G\right)=Z\left(G\right)+2S\left(G\right)+4T\left(G\right),$

其中$Z\left(G\right)$ 表示图$\text{G}$ 的Hosoya指标，$S\left(G\right)$ 是图G包含一个圈的Sachs图$T\left(G\right)$ 是图$\text{G}$ 包含两个圈的Sachs图，并证明了计算图的永久和的递推公式，进一步确定了单圈图的永久和的上界和下界以及对应的极图[15]。证明了图的完美匹配数是斜邻接矩阵的积和式的平均值。此外，还发现图的匹配多项式是方向图的斜积和多项式的期望值。吴廷增和So [5]介绍了永久和的性质，刻画了单圈图永久和极值的第二大和第二小以及对应的极图，指出了图的永久和与斐波那契数列密切相关，并证明了永久和的计算是$\#p$ -完全问题。吴廷增和Das [8]证明了双圈图的永久和的极大值和极小值，并完全刻画了对应的极图。[16] [17]介绍了积和式在化学图论中主要用于计算分子图的完美匹配数(凯库勒结构数)，这在化学中具有重要意义。在[18]中介绍了积和式与分子图的拓扑指标(如Hosoya指数)的关系。

1.2. 课题的提出

永久和作为近年来新提出的一个拓扑指标，吴廷增和赖虹建给出了永久和的定义，即积和式多项式的所有系数的绝对值之和，还系统地介绍了永久和的性质。在数学中也有重要的研究价值，有大量的问题值得进一步研究。吴廷增，任胜章和Das等研究了二部图的永久和，在这个基础上，我们进一步研究完全二部图的永久和，并讨论几乎正则完全正则二部图删边子图的永久和.这对二部图永久和的研究是一个有意义的补充。

2. 完全二部图及删星子图的永久和

本文主要介绍了几乎正则完全二部图的永久和，并给出其计算公式。为了方便，几乎正则完全二部图用$K_{p,p}$ 表示，几乎正则二部图用$K_{p,q}$ 表示，$S_p$ 表示有$\text{s}$ 条边的星$K_{1,s}$ 。

设$Q_{s,n}$ 是从$1,2,\dots ,\text{n}$ 中选择的严格增长的$\text{s}$ 整数序列整体，$M\left[\alpha |\beta \right]$ 是用行数$\alpha$ 和列数$\beta$ 表示$\text{M}$ 的子矩阵，$M\left(\alpha |\beta \right)$ 表示$\text{M}$ 的子矩阵，其中行与$\alpha$ 互补，列与$\beta$ 互补。

引理2.1. [19]设$\text{M}$ 是一个$n\times n$ 矩阵，并且$\alpha \in Q_{s,n}$ ，则

$\text{per}\left(M\right)={\displaystyle \sum }_{\beta \in Q_{s,n}}\text{per}\left(M\left[\alpha |\beta \right]\right)\text{per}\left(M\left(\alpha |\beta \right)\right).$

引理2.2. [19]设$M_1$ 和$M_1$ 都是$n\times n$ 矩阵，则

$\text{per}\left(M_1+M_2\right)={\displaystyle \sum }_{s=0}^n{\displaystyle \sum }_{\beta \in Q_{s,n}}\text{per}\left(M_1\left[\alpha |\beta \right]\right)\text{per}\left(M_2\left(\alpha |\beta \right)\right).$

其中当$s=0$ 时$\text{per}\left(M_1\left[\alpha |\beta \right]\right)=1$ 。

2.1. 完全二部图的永久和

定理2.1.1. 当$p\ge q$ 时，$PS\left(K_{p,q}\right)+{\displaystyle \sum }_{k=1}^q\left(\begin{array}{l}p\hfill \\ k\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ k\hfill \end{array}\right){\left(k!\right)}^2$ 。

证明:令$A\left(G_1\right)$ 为$K_{p,q}$ 的邻接矩阵，由于$PS(G)=per(I+A(G)).$ 当$p\ge q$ 时，矩阵$A\left(G_1\right)$ 皆为$\left(p+q\right)\times \left(p+q\right)$ 阶矩阵，则矩阵$A\left(G_1\right)$ 如下：

$A\left(G_1\right)={\left(\begin{array}{cccccc}& & & & & \\ 0& \cdots & 0& 1& \cdots & 1\\ & & & & & \\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ & & & & & \\ 0& \cdots & 0& 1& \cdots & 1\\ & & & & & \\ 1& \cdots & 1& 0& \cdots & 0\\ & & & & & \\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ & & & & & \\ 1& \cdots & 1& 0& \cdots & 0\end{array}\right)}_{\left(p+q\right)\times \left(p+q\right)}$

由引理2.2得：

$PS\left(K_{p,q}\right)=\mathrm{per}\left(M_1+M_2\right)=\mathrm{per}\left(I\right)\times 1+\left(\begin{array}{l}p\hfill \\ 1\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 1\hfill \end{array}\right)\times \mathrm{per}\left[\begin{array}{ll}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]+\left(\begin{array}{l}p\hfill \\ 2\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 2\hfill \end{array}\right)\times \mathrm{per}\left[\begin{array}{llll}0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \end{array}\right]+\left(\begin{array}{l}p\hfill \\ 3\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 3\hfill \end{array}\right)$ .$\times \mathrm{per}\left[\begin{array}{cccccc}0& 0& 0& 1& 1& 1\\ 0& 0& 0& 1& 1& 1\\ 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 0\\ 1& 1& 1& 0& 0& 0\end{array}\right]+\cdots +\left(\begin{array}{c}p\\ q\end{array}\right)\left(\begin{array}{l}q\hfill \\ q\hfill \end{array}\right)\times \mathrm{per}\left[\begin{array}{cccccc}0& \cdots & 0& 1& \cdots & 1\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 0& \cdots & 0& 1& \cdots & 1\\ 1& \cdots & 1& 0& \cdots & 0\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 1& \cdots & 1& 0& \cdots & 0\end{array}\right]+\mathrm{per}\left(A\left(G_1\right)\right)$

$\begin{array}{l}=1+\left(\begin{array}{l}p\hfill \\ 1\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 1\hfill \end{array}\right)\times 1+\left(\begin{array}{l}p\hfill \\ 2\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 2\hfill \end{array}\right)\times {\left(2!\right)}^2+\left(\begin{array}{l}p\hfill \\ 3\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ 3\hfill \end{array}\right)\times {\left(3!\right)}^2+\cdots +\left(\begin{array}{l}p\hfill \\ q\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ q\hfill \end{array}\right)\times {\left(q!\right)}^2\\ =1+{\displaystyle \sum _{k=1}^q\left(\begin{array}{l}p\hfill \\ k\hfill \end{array}\right)}\left(\begin{array}{l}q\hfill \\ k\hfill \end{array}\right){\left(k!\right)}^2.\end{array}$

2.2. 几乎正则完全二部图删星子图的永久和

定理2.2.1. 当$\text{p}\ge \text{q}$ ，$且i<k+1$ 时，

$\begin{array}{l}PS\left(K_{p,p}-E\left(K_{1,q}\right)\right)=1+p^2-q+{\displaystyle \sum _{k=1}^{p-1}\left(\begin{array}{c}p-1\\ k\end{array}\right)}\{{\displaystyle \sum _{i=1}^{p-q}\left(\begin{array}{c}p-q\\ i\end{array}\right)}\left(\begin{array}{c}p\\ k+1-i\end{array}\right)\times {\left(k!\times i\right)}^2\\ +\left[\left(\begin{array}{c}p-q\\ i+1\end{array}\right)+\left(\begin{array}{c}p\\ i+1\end{array}\right)\right]\times {\left[\left(i+1\right)\right]}^2\}+{\left[\left(p-q\right)!\times \left(p-q\right)\right]}^2.\end{array}$

证明：$\text{I}$ 为单位矩阵，$K_{p,p}$ 删去星$K_{1,q}$ 得到的图的邻接矩阵记为$A\left(G_2\right),\text{I}$ 和$A\left(G_2\right)$ 皆为$2p\times 2p$ 阶矩阵。

$A\left(G_2\right)={\left(\begin{array}{cccccccccc}0& \cdots & \cdots & \cdots & 0& 0& \cdots & 0& \cdots & 1\\ 0& \cdots & \cdots & \cdots & 0& 1& \cdots & \cdots & \cdots & 1\\ ⋮& \ddots & \ddots & \ddots & ⋮& ⋮& \ddots & \ddots & \ddots & ⋮\\ 0& \cdots & \cdots & \cdots & 0& 1& \cdots & \cdots & \cdots & 1\\ 0& 1& \cdots & \cdots & 1& 0& \cdots & \cdots & \cdots & 0\\ ⋮& ⋮& \cdots & \cdots & ⋮& 0& \cdots & \cdots & \cdots & 0\\ 0& 1& \cdots & \cdots & 1& 0& \cdots & \cdots & \cdots & 0\\ 1& 1& \ddots & \ddots & 1& 0& \ddots & \ddots & \ddots & 0\\ ⋮& ⋮& \ddots & \ddots & ⋮& ⋮& \ddots & \ddots & \ddots & ⋮\\ 1& 1& \cdots & \cdots & 1& 0& \cdots & \cdots & \cdots & 0\end{array}\right)}_{2p\times 2p}$

当$p\ge q$ $且i<k+1$ 时，由引理2.2得：

$PS\left(K_{p,p}-E\left(K_{1,q}\right)\right)=\mathrm{per}\left(I\right)+\left(\left(\begin{array}{c}p-q\\ 1\end{array}\right)+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{l}p\hfill \\ 1\hfill \end{array}\right)\right)\times \mathrm{per}\left[\begin{array}{ll}0\hfill & 1\hfill \\ 1\hfill & 0\hfill \end{array}\right]+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{l}q\hfill \\ 1\hfill \end{array}\right)\times \left(\begin{array}{c}p-q\\ 1\end{array}\right)$

$\times \text{per}\left[\begin{array}{llll}0\hfill & 0\hfill & 0\hfill & 1\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \end{array}\right]+\left(\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p\\ 2\end{array}\right)\right)\times \mathrm{per}\left[\begin{array}{llll}0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \end{array}\right]$

$\begin{array}{l}+\left(\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p\\ 2\end{array}\right)\right)\times \mathrm{per}\left[\begin{array}{llll}0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 0\hfill \end{array}\right]+\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{c}q\\ 2\end{array}\right)\left(\begin{array}{c}p-q\\ 1\end{array}\right)\\ +\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{l}q\hfill \\ 1\hfill \end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)\times \mathrm{per}\left[\begin{array}{llllll}0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right]+(\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{c}p-q\\ 3\end{array}\right)+\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{l}p\hfill \\ 4\hfill \end{array}\right))\end{array}$

$\mathrm{per}\left[\begin{array}{llllllll}0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right]+\cdots +(\left(\begin{array}{l}p-1\hfill \\ p-1\hfill \end{array}\right)\left(\begin{array}{l}p-q\hfill \\ p-q\hfill \end{array}\right)+\left(\begin{array}{c}p-1\\ p-1\end{array}\right)\left(\begin{array}{c}p\\ p-1\end{array}\right))\times$

$\mathrm{per}{\left[\begin{array}{cccccc}0& \cdots & 0& 1& \cdots & 1\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 0& \cdots & 0& 1& \cdots & 1\\ 1& \cdots & 1& 0& \cdots & 0\\ ⋮& \ddots & ⋮& ⋮& \ddots & ⋮\\ 1& \cdots & 1& 0& \cdots & 0\end{array}\right]}_{\left(p-1\right)\times \left(p-1\right)}+\mathrm{per}\left(A\left(G_2\right)\right)$

$\begin{array}{l}=1+\left(\left(\begin{array}{c}p-q\\ 1\end{array}\right)+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p\\ 1\end{array}\right)\right)\times {\left(1!\right)}^2+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}q\\ 1\end{array}\right)\left(\begin{array}{c}p-q\\ 1\end{array}\right)\times {\left(1!\times 1\right)}^2\\ +\left(\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)+\left(\begin{array}{c}p-1\\ 1\end{array}\right)\left(\begin{array}{l}p\hfill \\ 2\hfill \end{array}\right)\right)\times {\left(2!\right)}^2+\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{c}q\\ 2\end{array}\right)\left(\begin{array}{c}p-q\\ 1\end{array}\right)\times {\left(2!\times 1\right)}^2\end{array}$

$\begin{array}{l}+\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{c}q\\ 1\end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)\times {\left(2!\times 2\right)}^2+(\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{c}p-q\\ 3\end{array}\right)+\left(\begin{array}{c}p-1\\ 2\end{array}\right)\left(\begin{array}{l}p\hfill \\ 3\hfill \end{array}\right))\times {\left(3!\right)}^2\\ +\left(\begin{array}{c}p-1\\ 3\end{array}\right)\left(\begin{array}{l}q\hfill \\ 3\hfill \end{array}\right)\left(\begin{array}{c}p-q\\ 1\end{array}\right)\times {\left(3!\times 1\right)}^2+\left(\begin{array}{c}p-1\\ 3\end{array}\right)\left(\begin{array}{l}q\hfill \\ 2\hfill \end{array}\right)\left(\begin{array}{c}p-q\\ 2\end{array}\right)\times {\left(3!\times 2\right)}^2\\ +\left(\begin{array}{c}p-1\\ 3\end{array}\right)\left(\begin{array}{l}q\hfill \\ 1\hfill \end{array}\right)\left(\begin{array}{c}p-q\\ 3\end{array}\right)\times {\left(3!\times 3\right)}^2+\left(\left(\begin{array}{c}p-1\\ 3\end{array}\right)\left(\begin{array}{c}p-q\\ 4\end{array}\right)+\left(\begin{array}{c}p-1\\ 3\end{array}\right)\left(\begin{array}{c}p\\ 4\end{array}\right)\right)\\ \times {\left(4!\right)}^2+\cdots +\left(\left(\begin{array}{c}p-1\\ p-1\end{array}\right)\left(\begin{array}{c}p-q\\ p-q\end{array}\right)+\left(\begin{array}{l}p-1\hfill \\ p-1\hfill \end{array}\right)\left(\begin{array}{c}p\\ p-1\end{array}\right)\right)\times {\left[\left(p-1\right)!\right]}^2\\ +\left(\begin{array}{l}p-1\hfill \\ p-1\hfill \end{array}\right)\left(\begin{array}{l}q\hfill \\ q\hfill \end{array}\right)\left(\begin{array}{c}p-q\\ p-q\end{array}\right)\times {\left[\left(p-q\right)!\times \left(p-q\right)\right]}^2.\end{array}$

$\begin{array}{l}=1+p^2-q+{\displaystyle \sum _{k=1}^{p-1}\left(\begin{array}{c}p-1\\ k\end{array}\right)}\{{\displaystyle \sum _{i=1}^{p-q}\left(\begin{array}{c}p-q\\ i\end{array}\right)}\left(\begin{array}{c}p\\ k+1-i\end{array}\right)\times {\left(k!\times i\right)}^2+\\ +\left[\left(\begin{array}{c}p-q\\ i+1\end{array}\right)+\left(\begin{array}{c}p\\ i+1\end{array}\right)\right]\times {\left[\left(i+1\right)\right]}^2\}+{\left[\left(p-q\right)!\times \left(p-q\right)\right]}^2.\end{array}$

3. 有向树的积和谱

这一节中我们给出了一类二部图无向树与有向树的积和谱的关系。

引理3.1 [20]：设G是一个图。那么对于任意定向图$G^{\sigma }$ ，其积和谱Sp有如下关系，即iSp (G) = Sp ($G^{\sigma }$ )当且仅当G是无圈的。

引理3.2 (巴里克，纽曼和帕蒂[21]，引理2.3)：设T是一个非奇异的树，$T^{ -1}$ 是其逆图。那么T的邻接矩阵的逆矩阵通过一个±1的对角矩阵与$T^{ -1}$ 的邻接矩阵相似。

定理3.3：设T为一棵具有完美匹配的树，且$T^{\sigma }$ 为T的任意方向。则Sp (${\left(T^{\sigma }\right)}^{-1}$ ) = iSp ($T^{ -1}$ )。

证明：设${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ 为T的所有积和根。由引理3.2知，由于T是非奇异的，因此${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ 均非零，并且$Sp\left(T^{ -1}\right) =\left\{\frac{1}{{\lambda }_1},\frac{1}{{\lambda }_2},\cdots ,\frac{1}{{\lambda }_n}\right\}$ ，由于T是一棵树，由引理3.1我们有Sp ($T^{\sigma }$ ) = $\left\{{\lambda }_{1}i,{\lambda }_{2}i,\cdots ,{\lambda }_{n}i\right\}$ 。因此Sp (${\left(T^{\sigma }\right)}^{-1}$ ) = $\left\{-\frac{1}{{\lambda }_1}i,-\frac{1}{{\lambda }_2}i,\cdots ,-\frac{1}{{\lambda }_n}i\right\}=\left\{\frac{1}{{\lambda }_1}i,\frac{1}{{\lambda }_2}i,\cdots ,\frac{1}{{\lambda }_n}i\right\}$ ，${(T^{\sigma })}^{-1}$ 的斜邻接矩阵是$T^{\sigma }$ 的斜邻接矩阵的逆矩阵，且T的每个积和根的负数也是T的积和根。因此Sp (${\left(T^{\sigma }\right)}^{-1}$ ) = iSp ($T^{ -1}$ )。

4. 总结与展望

4.1. 总结

本文结合了积和式和永久和的基本性质，通过引用一些定义讨论了完全二部图的永久和的计算公式，并给出了一些完全正则二部图的删边子图的永久和的表达式以及树的定向图与无向图的积和谱的关系。

4.2. 展望

通过梳理文献资料，永久和的定义自提出以来便不断受到学者们的重视，其研究发文量总体呈递增趋势，发展速度和研究热度都在不断上升。在此基础之上，我们期待用新的方法去研究完全多部图的永久和。

基金项目

青海民族大学研究生创新项目《定向图的积和多项式的若干问题研究》，项目编号：07M2024012。