中文

Operations Research Transactions >

2023 , Vol. 27 >Issue 3: 150 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.03.012

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

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

Received date: 2019-12-19

  Online published: 2023-09-14

Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.012

References

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.
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.
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.
8 Dehmer M , Ili? A . Location of zeros of Wiener and distance polynomials[J]. Plos One, 2012, 7 (3): e28328.
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.
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.
12 Ghorbani E . Graphs with few matching roots[J]. Graphs and Combinatorics, 2013, 29, 1377- 1389.
13 Zhang H L , Yu G L , Li S L . Graphs with six distinct matching roots[J]. Information Processing Letters, 2015, 115, 521- 526.
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.
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.
16 Anuradha A , Balakrishnan R , So W . Skew spectra of graphs without even cycles[J]. Linear Algebra and its Applications, 2014, 444, 67- 80.
17 Wang W H , Xu W W . Graphs with the maximal Estrada indices[J]. Linear Algebra and its Applications, 2014, 446, 314- 328.
18 肖毛, 王文环. 不含偶圈双圈图的极小斜能量[J]. 运筹学学报, 2014, 18, 85- 95.
19 Chen X L , Li X L , Lian H S . The matching energy of random graphs[J]. Discrete Applied Mathematics, 2015, 193, 102- 109.
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.
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.
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.
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.
Options
Outlines

/

〈 〉