小直徑雙圈圖的永久和

蔚勇　吳廷增

摘要：研究了小直徑雙圈圖永久和的性質，確定了直徑為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