小直径单圈图的永久和指标的极值研究
Extremal Unicyclic Graphs of the Small Diameter with Respect to Permanental Sum
DOI: 10.12677/PM.2021.1111216, PDF, HTML, 下载: 276  浏览: 382  科研立项经费支持
作者: 白英刚：青海民族大学数学与统计学院，青海 西宁
关键词: 积和多项式；永久和；Hosoya指标；单圈图；Permanental Polynomial； Permanental Sum； Hosoya Index； Unicyclic Graph
摘要: 令 G 表示一个 n 个顶点的图。 图的永久和是指图的积和多项式系数的绝对值之和。 图的永久和的计算被证明是#p- 完全的。 本文中，刻画了直径为 3 和 4 单圈图的永久和的界，并给出了达到该界的极图。
Abstract: Let G be a graph with n vertex, the permanental sum of G is the sum of the absolute valutes of the cofficients. Computing the permanental polynomials of graphs is #p. In this paper, we will determine the graph minimizing the permanental sum among all unicyclic graphs with diameter 3 and 4 , and the corresponding extremal bicyclic graphs are also determined.
文章引用：白英刚. 小直径单圈图的永久和指标的极值研究[J]. 理论数学, 2021, 11(11): 1933-1948. https://doi.org/10.12677/PM.2021.1111216

参考文献

[1] 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
[2] Kasum, D., Trinajsti´c, N. and Gutman, I. (1981) Chemical Graph Theory. III. On Permanental Polynomial. Croatica Chemica Acta, 54, 321-328.
[3] Cash, G.G. (2000) The Permanental Polynomial. Journal of Chemical Information and Modeling Sciences, 40, 1203-1206.
https://doi.org/10.1021/ci000031d
[4] Cash, G.G. (2000) Permanental Polynomials of Smaller Fullerenes. Journal of Chemical Information and Modeling Sciences, 40, 1207-1209.
https://doi.org/10.1021/ci0000326
[5] Chen, R. (2004) A Note on the Relations between the Permanental and Characteristic Polynomials of Coronoid Hydrocarbons. MATCH Communications in Mathematical and in Computer Chemistry, 51, 137-148.
[6] Chou, Q., Liang, H. and Bai, F. (2011) Remarks on the Relations between the Permanental and Characteristic Polynomials of Fullerenes. MATCH Communications in Mathematical and in Computer Chemistry, 66, 743-750.
[7] Dehmer, M., et al. (2017) Highly Unique Network Descriptors Based on the Roots of the Permanental Polynomial. Information Sciences, 408, 176-181.
https://doi.org/10.1016/j.ins.2017.04.041
[8] Gutman, I. and Cash, G.G. (2002) Relations between the Permanental and Characteristic Polynomials of Fullerenes and Benzenoid Hydro-Carbons. MATCH Communications in Mathematical and in Computer Chemistry, 45, 55-70.
[9] Liang, H., Tong, H. and Bai, F. (2008) Computing the Permanental Polynomial of C60 in Parallel. MATCH Communications in Mathematical and in Computer Chemistry, 60, 349- 358.
[10] Shi, Y., Dehmer, M., Li, X. and Gutman, I. (2016) Graph Polynomials. CRC Press, Boca Raton.
https://doi.org/10.1201/9781315367996
[11] Wu, T. and Lai, H. (2018) On the Permanental Nullity and Matching Number of Graphs. Linear and Multilinear Algebra, 66, 516-524.
https://doi.org/10.1080/03081087.2017.1302403
[12] Yan, W. and Zhang, F. (2004) On the Permanental Polynomial of Some Graphs. Journal of Mathematical Chemistry, 35, 175-188.
https://doi.org/10.1023/B:JOMC.0000033254.54822.f8
[13] Yu, G. and Qu, H. (2018) The Coefficients of the Immanantal Polynomial. Applied Mathematics and Computation, 339, 38-44.
https://doi.org/10.1016/j.amc.2018.06.057
[14] Zhang, H. and Li, W. (2012) Computing the Permanental Polynomials of Bipartite Graphs by Pfaffian Orientation. Discrete Applied Mathematics, 160, 2069-2074.
https://doi.org/10.1016/j.dam.2012.04.007
[15] Xie, S., et al. (2004) Capturing the Labile Fullerene[50] as C50CI10. Science, 304, 699.
https://doi.org/10.1126/science.1095567
[16] Tong, H., Liang, H. and Bai, F. (2006) Permanental Polynomials of the Larger Fullerenes. MATCH Communications in Mathematical and in Computer Chemistry, 56, 141-152.
[17] Wu, T. and So, W. (2019) Unicyclic Graphs with Second Largest and Second Smallest Permantal Sums. Applied Mathematics and Computation, 351, 168-175.
https://doi.org/10.1016/j.amc.2019.01.056
[18] 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.
[19] Li, W., Qin, Z. and Zhang, H. (2016) Extremal Hexagonal Chains with Respect to the Coefficients Sum of the Permanental Polynomial. Applied Mathematics and Computation, 291, 30-38.
https://doi.org/10.1016/j.amc.2016.06.025
[20] Li, S. and Wei, W. (2018) Extremal Octagonal Chains with Respect to the Coefficients Sum of the Permanental Polynomial. Applied Mathematics and Computation, 328, 45-57.
https://doi.org/10.1016/j.amc.2018.01.033
[21] Wu, T. and Lai, H. (2018) On the Permanental Sum of Graphs. Applied Mathematics and Computation, 331, 334-340.
https://doi.org/10.1016/j.amc.2018.03.026
[22] Li, W., Qin, Z. and Wang, Y. (2020) Enumeration of Permanental Sums of Lattice. Applied Mathematics and Computation, 370, Article ID: 124914.
https://doi.org/10.1016/j.amc.2019.124914
[23] Wu, T. and L口, H. (2019) The Extremal Permanental Sum for a Quasi-Tree Graph. Complexity, 2019, Article ID: 4387650.
https://doi.org/10.1155/2019/4387650
[24] Wu, T., Ren, S. and Das, K. (2019) Some Extremal Graphs with Respect to Permanental Sum. Bulletin of the Malaysian Mathematical Sciences Society, 42, 2947-2961.
https://doi.org/10.1007/s40840-018-0642-9 [25] Wu, T. and Das, K. (2020) On the Permanental Sum of Bicyclic Graphs. Computational and Applied Mathematics, 39, Article No. 72.
https://doi.org/10.1007/s40314-020-1108-x
[25] Hosoya, H. (1971) Topological Index, a Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons. Bulletin of the Chemical Society of Japan, 44, 2332-2339.
https://doi.org/10.1246/bcsj.44.2332
[26] Feng, L., Li, Z., Liu, W., Lu, L. and Stevanovi´c, D. (2020) Minimal Harary Index of Unicyclic Graphs with Diameter at Most 4. Applied Mathematics and Computation, 381, Article ID: 125315.
https://doi.org/10.1016/j.amc.2020.125315
[27] Wu, T.Z. and So, W. (2019) Unicyclic Graphs with Second Largest and Second Smallest Permanental Sums. Applied Mathematics and Computation, 351, 168-175.
https://doi.org/10.1016/j.amc.2019.01.056

为你推荐