不含偶圈(n, m)-图匹配多项式的最大根

doi:10.15960/j.cnki.issn.1007-6093.2023.03.012

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 150-158.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.012

不含偶圈(n, m)-图匹配多项式的最大根

袁玲¹, 王文环¹^,*()

1. 上海大学数学系, 上海 200444

收稿日期:2019-12-19 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 王文环 E-mail:whwang@shu.edu.cn
作者简介:王文环, E-mail: whwang@shu.edu.cn
基金资助:
国家自然科学基金(11001166)

On the largest root of the matching polynomials of (n, m)-graphs without even cycles

Ling YUAN¹, Wenhuan WANG¹^,*()

1. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received:2019-12-19 Online:2023-09-15 Published:2023-09-14
Contact: Wenhuan WANG E-mail:whwang@shu.edu.cn

摘要/Abstract

摘要：

令图$G$ 是具有$n$个顶点的简单连通图。图$G$ 的匹配多项式定义为$\sum_{k=0}^{[n/2]}(-1)^k$ $m(G, k)x^{n-2k}$, 其中$m(G, k)$ 是图$G$ 中$k$-匹配的数目, $0\leq k\leq [n/2]$。令$\Phi_{n, m}$ 是具有$n$ 个顶点和$m$ 条边的不含偶圈图的集合, 其中$n\leq m\leq \frac{3(n-1)}{2}$。本文介绍了四个新的比较匹配多项式最大根的变换方法, 从而刻画了$\Phi_{n, m}$ 中具有匹配多项式最大根的图。

关键词: 匹配多项式, 最大根, (n, m)-图, 偶圈

Abstract:

Let $G$ be a simple connected graph with $n$ vertices. The matching polynomial of $G$ is given by $\sum_{k=0}^{[n/2]}(-1)^km(G, k)x^{n-2k}$, where $m(G, k)$ is the number of $k$-matchings in $G$ with $0\leq k\leq [n/2]$. Let $\Phi_{n, m}$ be the set of graphs with $n$ vertices and $m$ edges having no even cycles, where $n\leq m\leq \frac{3(n-1)}{2}$. In this paper, four new transformations for comparing the largest roots of matching polynomials are introduced and the graph with the largest root of matching polynomial is characterized among graphs in $\Phi_{n, m}$.

Key words: matching polynomial, the largest root, (n, m)-graph, even cycles

中图分类号:

袁玲, 王文环. 不含偶圈(n, m)-图匹配多项式的最大根[J]. 运筹学学报, 2023, 27(3): 150-158.

Ling YUAN, Wenhuan WANG. On the largest root of the matching polynomials of (n, m)-graphs without even cycles[J]. Operations Research Transactions, 2023, 27(3): 150-158.

图/表 5

参考文献 28

1	Cvetković D M , Doob M , Gutman I , et al. Recent Results in the Theory of Graph Spectra[M]. Amsterdam: North-Holland, 1988.
2	Godsil C D . Algebraic Combinatorics[M]. London: Chapman and Hall, 1993.
3	Godsil C D , Gutman I . On the theory of the matching polynomial[J]. Journal of Graph Theory, 1981, 5, 137- 144. doi: 10.1002/jgt.3190050203
4	Gutman I. A Survey on the Matching Polynomial[M]. in: M. Dehmer, T. Y. Shi, I. Gutman, L. X. Li (Eds. ), Graph Polynomials, CRC Press, Boca Raton, 2016, 73-95.
5	Heilmann O J , Lieb E H . Monomers and dimers[J]. Physical Review Letters, 1970, 24, 1412- 1414. doi: 10.1103/PhysRevLett.24.1412
6	Kunz H . Location of the zeros of the partition function for some classical lattice systems[J]. Physics Letters, 1970, 32A, 311- 312.
7	Fisher D C , Ryan J . Bounds on the largest root of the matching polynomial[J]. Discrete Mathematics, 1992, 110, 275- 278. doi: 10.1016/0012-365X(92)90718-U
8	Dehmer M , Ilić A . Location of zeros of Wiener and distance polynomials[J]. Plos One, 2012, 7 (3): e28328. doi: 10.1371/journal.pone.0028328
9	Dehmer M , Shi Y T , Mowshowitz A . Discrimination power of graph measures based on complex zeros of the partial Hosoya polynomial[J]. Applied Mathematics and Computation, 2015, 250, 352- 355. doi: 10.1016/j.amc.2014.10.048
10	Gutman I . A note on analogies between the characteristic and the matching polynomial of a graph[J]. Publications de l'institut Mathématique, 1982, 31 (45): 27- 31.
11	Zhang H L , Lin R F , Yu G L . The largest matching root of unicyclic graphs[J]. Information Processing Letters, 2013, 113, 804- 806. doi: 10.1016/j.ipl.2013.07.003
12	Ghorbani E . Graphs with few matching roots[J]. Graphs and Combinatorics, 2013, 29, 1377- 1389. doi: 10.1007/s00373-012-1186-7
13	Zhang H L , Yu G L , Li S L . Graphs with six distinct matching roots[J]. Information Processing Letters, 2015, 115, 521- 526. doi: 10.1016/j.ipl.2014.10.012
14	Zhang H L , Chen G T . The largest matching roots of unicyclic graphs with a fixed matching number[J]. Cogent Mathematics, 2017, 4, 1280912. doi: 10.1080/23311835.2017.1280912
15	Liu W J , Guo Q , Zhang Y B , et al. Further results on the largest matching root of unicyclic graphs[J]. Discrete Applied Mathematics, 2017, 221, 82- 88. doi: 10.1016/j.dam.2016.12.022
16	Anuradha A , Balakrishnan R , So W . Skew spectra of graphs without even cycles[J]. Linear Algebra and its Applications, 2014, 444, 67- 80. doi: 10.1016/j.laa.2013.11.030
17	Wang W H , Xu W W . Graphs with the maximal Estrada indices[J]. Linear Algebra and its Applications, 2014, 446, 314- 328. doi: 10.1016/j.laa.2013.12.034
18	肖毛, 王文环. 不含偶圈双圈图的极小斜能量[J]. 运筹学学报, 2014, 18, 85- 95. doi: 10.3969/j.issn.1007-6093.2014.04.009
19	Chen X L , Li X L , Lian H S . The matching energy of random graphs[J]. Discrete Applied Mathematics, 2015, 193, 102- 109. doi: 10.1016/j.dam.2015.04.022
20	Chen L , Liu J F . The bipartite unicyclic graphs with the first $\lfloor \frac{n-3}{4}\rfloor$ largest matching energies[J]. Applied Mathematics and Computation, 2015, 268, 644- 656. doi: 10.1016/j.amc.2015.06.115
21	Chen L , Liu J F , Shi Y T . Matching energy of unicyclic and bicyclic graphs with a given diameter[J]. Complexity, 2015, 21, 224- 238. doi: 10.1002/cplx.21599
22	Chen L , Liu J F , Shi Y T . Bounds on the matching energy of unicyclic odd-cycle graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2016, 75, 315- 330.
23	Chen L , Shi Y T . The maximal matching energy of tricyclic graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2015, 73, 105- 120.
24	Gutman I , Wagner S . The matching energy of a graph[J]. Discrete Applied Mathematics, 2012, 160, 2177- 2187. doi: 10.1016/j.dam.2012.06.001
25	Wang W H , So W . On minimum matching energy of graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2015, 74, 399- 410.
26	Xu K X , Das K C , Zheng Z Q . The minimal matching energy of (n, m)-graphs with a given matching number[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2015, 73, 93- 104.
27	Li J , Li X L , Lian H S . Extremal skew energy of digraphs with no even cycles[J]. Transactions on Combinatorics, 2014, 3, 37- 49.
28	Zhang H L , Shu J L . On the matching polynomial of theta graphs[J]. Ars Combinatoria, 2012, 105, 477- 490.

不含偶圈(n, m)-图匹配多项式的最大根

On the largest root of the matching polynomials of (n, m)-graphs without even cycles

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 28

相关文章 1

编辑推荐

Metrics

本文评价