小直径双圈图的永久和

蔚勇　吴廷增

摘要：研究了小直径双圈图永久和的性质，确定了直径为2的双圈图永久和的界。特别地，确定了直径为3的双圈图的永久和上界，并刻画了其极图。

关键词：积和式；积和多项式；永久和；直径；双圈图

中图分类号：O157.5 文献标志码：A

3 结论

本文刻画了直径为2与3的双圈图的永久和的界，为小直径图永久和及其它拓扑指标的研究提供了一定的思路。

参考文献

［1］BONDY J A，MURTY U S R. Graph theory with applications［M］. New York： North-Holland，1976.

［2］VLIANT L G. The complexity of computing the permanent［J］. Theoretical Computer Science，1979， 8：189-201.

［3］CASH G G. The permanental polynomial［J］. Journal of Chemical Information and Computer Sciences，2000，40：1203-1206.

［4］CASH G G. Permanental polynomials of smaller fullerenes［J］. Journal of Chemical Information and Computer Sciences，2000，40：1207-1209.

［5］LIANG H，TONG H. BAI F S. Computing the permanental polynomial of C60 in parallel［J］. Match-Communications in Mathematical and in Computer Chemistry，2008，60：349-358.

［6］KASUM D，TRINAJSTI N，GUTMAN I. Chemical graph theory. III. On permanental polynomial［J］. Croatica Chemica acta， 1981， 54： 321-328.

［7］SHI Y T， DEHMER M，LI X L，et al. Graph polynomials［M］. Florida： Crc Press，2016.

［8］YAN W G， ZHANG F J. On the permanental polynomial of some graphs［J］. Journal of Mathematical Chemistry，2004，35：175-188.

［9］ZHANG H P，LI W. Computing the permanental polynomials of bipartite graphs by Pfaffian orientation［J］. Discrete Applied Mathematics，2012，160： 2069-2074.

［10］ MERRIS R，REBMAN K R，WATKINS W. Permanental polynomials of graphs［J］. Linear Algebra and its Applications，1981，38： 273-288.

［11］ WU T Z， SO W. Unicyclic graphs with second largest and second smallest permantal sums［J］. Applied Mathematics and Computation， 2019， 351：168-175.

［12］ 仝辉.稀疏矩阵积和式与积和多项式的并行算法［D］.北京：清华大学，2006.

［13］ XIE S Y， GAO F， LU X， et al. Capturing the labile fullerene［50］ as C50Cl10［J］. Science， 2004， 304： 699.

［14］ WU T Z， LAI H J. On the permanental sum of graphs［J］. Applied Mathematics and Computation， 2018， 331： 334-340.

［15］ LI W，QIN Z M，ZHANG H P. Extremal hexagonal chains with respect to the coefficients sum of the perman-ental polynomial［J］. Applied Mathematics and Computation，2016，291：30-38.

［16］ SO W， WU T Z， L H Z. Sharp bounds on the permanental sum of a graph［J］. Graphs and Combinatorics， 2021， 37，6：2421-2437.

［17］ TANG K，LI Q，DENG H. On the permanental polynomial and permanental sum of signed graphs［J］. Discrete Mathematics Letters， 2022，10：14-20.

［18］ WAGNER S，GUTMAN I. Maxima and minima of the hosoya index and the merrifield-simmons index： A survey of results and techniques［J］. Acta Applicandae Mathematicae，2010，112：323-346.

［19］ WU T Z，YU Y. On the hosoya indices of bicyclic graphs with small diameter［J］. Journal of Chemistry，2021（4）：5555700.

On the Permanental Sums of Bicyclic Graphs with Small Diameter

YU Yong，WU Ting-zeng

（School of Mathematics and Statistics， Qinghai Minzu University， Xining 810007， China）

Abstract：The properties of permanental sums of bicyclic graphs with small diameter were studied，and the bound of permanental sums of bicyclic graphs with diameter two were determined. In particular， the sharp upper bound of the permanental sums of bicyclic graphs with diameter three were determined， and the corresponding extremal bicyclic graphs were also characterized.

Keywords：permanent; permanental polynomial; permanental sum; diameter; bicyclic graph

收稿日期：2022-09-11

基金項目：国家自然科学基金（批准号：12261071）资助；青海省自然科学基金（批准号：2020-ZJ-920）资助。

通信作者：吴廷增，男，博士，教授，主要研究方向为图论与组合优化、复杂网络与数据科学等。E-mail：mathtzwu@163.com