不含4k-长圈二部图(斜)积和多项式的单峰性
Unimodality of (Skew-) Permanental Polynomials for Bipartite Graphs without 4k-Length Cycles
DOI: 10.12677/AAM.2025.1410434, PDF,   
作者: 蓟斗盖措毛：青海民族大学数学与统计学院，青海 西宁
关键词: 二部图；(斜)积和多项式；系数；单峰性；Bipartite Graphs； (Skew) Permanental Polynomials； Coefficient； Unimodality
摘要: 本文研究简单无向图及其定向图的代数性质。 通过为图中每条边赋予方向，可得到原图的一个定 向图。 基于原图的邻接矩阵可定义积和多项式，基于定向图的斜邻接矩阵则可定义斜积和多项式。 我们证明，对于不含四倍长圈的二部图，其积和多项式系数具有单峰性；进一步地，对这类图施 加特定定向后，其斜积和多项式系数也呈现单峰分布。
Abstract: This paper investigates the algebraic properties of simple undirected graphs and their oriented graphs. By assigning a direction to each edge of a graph, we obtain an orientation of the original graph. The permanent polynomial of the original graph is defined based on its adjacency matrix, while the skew permanent polynomial is defined based on the skew adjacency matrix of the oriented graph. We prove that for bipartite graphs without cycles of length a multiple of four, the coefficients of the permanent polynomial are unimodal. Furthermore, for such graphs under specific orientations, the coefficients of the skew permanent polynomial also exhibit unimodality.
文章引用：蓟斗盖措毛. 不含4k-长圈二部图(斜)积和多项式的单峰性[J]. 应用数学进展, 2025, 14(10): 214-226. https://doi.org/10.12677/AAM.2025.1410434

参考文献

[1] Valiant, L.G. (1979) The Complexity of Computing the Permanent. Theoretical Computer Science, 8, 189-201. [Google Scholar] [CrossRef] 
[2] Huh, J. (2012) Milnor Numbers of Projective Hypersurfaces and the Chromatic Polynomial of Graphs. Journal of the American Mathematical Society, 25, 907-927. [Google Scholar] [CrossRef] 
[3] Read, R.C. (1968) An Introduction to Chromatic Polynomials. Journal of Combinatorial Theory, 4, 52-71. [Google Scholar] [CrossRef] 
[4] Welsh, D. (1976) Matroid Theory. Academic Press.
[5] Heilmann, O.J. and Lieb, E.H. (1972) Theory of Monomer-Dimer Systems. Communications in Math- ematical Physics, 25, 190-232. [Google Scholar] [CrossRef] 
[6] Wang, Y. and Zhu, B. (2011) On the Unimodality of Independence Polynomials of Some Graphs. European Journal of Combinatorics, 32, 10-20. [Google Scholar] [CrossRef] 
[7] Brown, J.I. and Cameron, B. (2018) On the Unimodality of Independence Polynomials of Very Well- Covered Graphs. Discrete Mathematics, 341, 1138-1143. [Google Scholar] [CrossRef] 
[8] Zhu, B. and Wang, Q. (2019) Unimodality of Independence Polynomials of Rooted Products of Graphs. Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 150, 2573-2585. [Google Scholar] [CrossRef] 
[9] Zhu, B. (2016) Clique Cover Products and Unimodality of Independence Polynomials. Discrete Ap- plied Mathematics, 206, 172-180. [Google Scholar] [CrossRef] 
[10] Brown, J.I., Hickman, C.A. and Nowakowski, R.J. (2004) On the Location of Roots of Independence Polynomials. Journal of Algebraic Combinatorics, 19, 273-282. [Google Scholar] [CrossRef] 
[11] Zhu, B. (2018) Unimodality of Independence Polynomials of the Incidence Product of Graphs. Discrete Mathematics, 341, 2359-2365. [Google Scholar] [CrossRef] 
[12] Beaton, I. and Brown, J.I. (2020) On the Unimodality of Domination Polynomials.
https://arxiv.org/abs/2012.11813
[13] Kiani, D. and Mirzakhah, M. (2014) On the Log-Concavity of Laplacian Characteristic Polynomials of Graphs. The Electronic Journal of Linear Algebra, 27, 392-406. [Google Scholar] [CrossRef] 
[14] Schwenk, A.J. (1981) On Unimodal Sequences of Graphical Invariants. Journal of Combinatorial Theory, Series B, 30, 247-250. [Google Scholar] [CrossRef] 
[15] Kasum, D., Trinajsti´c, N. and Gutman, I. (1981) Chemical Graph Theory. III. On Permanental Polynomial. Croatica Chemica Acta, 54, 321-328.
[16] Merris, R., Rebman, K.R. and Watkins, W. (1981) Permanental Polynomials of Graphs. Linear Algebra and Its Applications, 38, 273-288. [Google Scholar] [CrossRef] 
[17] Liu, S. and Zhang, H. (2014) Permanental Polynomials of Skew Adjacency Matrices of Oriented Graphs.
https://arxiv.org/abs/1409.3036
[18] Li, W., Liu, S. and Zhang, H. (2014) A Note on the Permanental Roots of Bipartite Graphs. Discus- siones Mathematicae Graph Theory, 34, 49-56. [Google Scholar] [CrossRef] 
[19] Liu, S. (2017) On the Bivariate Permanent Polynomials of Graphs. Linear Algebra and Its Applica- tions, 529, 148-163. [Google Scholar] [CrossRef] 
[20] Lov´asz, L. and Plummer, M.D. (1986) Matching Theory. In: Annals of Discrete Mathematics, Vol. 29, North-Holland, 309-310.
[21] Li, W. (2021) On the Matching and Permanental Polynomials of Graphs. Discrete Applied Mathe- matics, 302, 16-23. [Google Scholar] [CrossRef] 
[22] Zhang, H. and Li, W. (2012) Computing the Permanental Polynomials of Bipartite Graphs by Pfaffian Orientation. Discrete Applied Mathematics, 160, 2069-2074. [Google Scholar] [CrossRef] 
[23] Yan, W. and Zhang, F. (2004) On the Permanental Polynomials of Some Graphs. Journal of Mathe- matical Chemistry, 35, 175-188. [Google Scholar] [CrossRef] 

为你推荐