|
|
Pure Mathematics 2025
图的积和多项式与匹配多项式的关系
|
Abstract:
令G是一个简单图,A(G)为图G的邻接矩阵.那么矩阵A(G)的永久和记为PS(A(G))，矩阵A(G)的积和多项式记为per(xI-A(G)).在本文中, 我们利用匹配多项式及其补图之间的相互关系，证明了图的积和多项式与其补图匹配多项式之间的关系；并且通过这个我们推导出了几乎完全图的永久和与其补图匹配数之间的具体关系.
Let G be a simple graph, and A(G) be the adjacency matrix of graph G. The permanent sum of matrix A(G) is denoted as P S(A(G)), and the permanental polynomial of matrix A(G) is denoted as per(xI ？ A(G)). In this paper, we utilize the interrelation between the matching polynomial and its complement graph to demonstrate the relationship between the permanental polynomial of a graph and the matching polynomial of its complement graph. Furthermore, through this approach, we deduce the specific re-lationship between the permanent sum of already complete graphs and the matching number of their complement graphs.
| [1] | Valiant, L.G. (1979) The Complexity of Computing the Permanent. Theoretical Computer
Science, 8, 189-201. https://doi.org/10.1016/0304-3975(79)90044-6 |
| [2] | Harary, F. (1969) Determinants, Permanents and Bipartite Graphs. Mathematics Magazine,
42, 146-148. https://doi.org/10.1080/0025570x.1969.11975950 |
| [3] | Minc, H. (1978) Permanents. Addison-Wesley. |
| [4] | Merris, R., Rebman, K.R. and Watkins, W. (1981) Permanental Polynomials of Graphs. Linear
Algebra and its Applications, 38, 273-288. https://doi.org/10.1016/0024-3795(81)90026-4 |
| [5] | Kasum, D., Trinajsti, N. and Gutman, I. (1981) Chemical Graph Theory. III. On the Perma nental Polynomial. Croatica Chemica Acta, 54, 321-328. |
| [6] | Borowiecki, M. and J_′zwiak, T. (1982) Computing the Permanental Polynomial of a Multi graph. Discussiones Mathematicae, 5, 9-16. |
| [7] | Wu, T. and Zhang, H. (2015) Some Analytical Properties of the Permanental Polynomial of a
Graph. Ars Combinatoria, CXIII, 261-267. |
| [8] | Chou, Q., Liang, H. and Bai, F. (2015) Computing the Permanental Polynomial of the High
Level Fullerene C70 with High Precision. MATCH Communications in Mathematical and in
Computer Chemistry, 73, 327-336. |
| [9] | Li, W. (2021) On the Matching and Permanental Polynomials of Graphs. Discrete Applied
Mathematics, 302, 16-23. https://doi.org/10.1016/j.dam.2021.05.030 |
| [10] | LovSsz, L. (2007) Combinatorial Problems and Exercises. Vol. 361, American Mathematical
Society. https://doi.org/10.1090/chel/361 |
| [11] | 马海成. 图的匹配多项式及其应用[M]. 北京: 科学出版社, 2019: 12. |
| [12] | Wu, T. and So, W. (2021) Permanental Sums of Graphs of Extreme Sizes. Discrete Mathe matics, 344, 112353. Article https://doi.org/10.1016/j.disc.2021.112353 |
