JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (6): 19-24.doi: 10.6040/j.issn.1671-9352.0.2023.041

•   • Previous Articles     Next Articles

Extremum of the matching maximum root of k-bridge graphs

Haicheng MA(),Xiaojie YOU   

  1. School of Mathematics and Statistics, Qinghai Minzu University, Xining 810007, Qinghai, China
  • Received:2023-10-30 Online:2024-06-20 Published:2024-06-17

RichHTML

0

PDF (PC)

193

Abstract:

Let G be a graph with n vertices, and μ(G, x) denote the matching polynomial of graph G, M1(G) denote the maximum root of the polynomial μ(G, x), which is called the matching maximum root. By identifying the first vertices and the last vertices of k paths Pa1+2, Pa2+2, …, Pak+2, respectively, the resulting graph is called the k-bridge graphs, denoted by θk(a1, a2, …, ak). A k-bridge graph with n vertices and nearly equal number of vertices on each paths is denoted as θk*(n). The following conclusions are proved. In all k-bridge graphs with n vertices, the matching maximum root to get the smallest graph is $\theta_k(0, \overbrace{1, 1 \cdots, 1}^{k-2}, n-k)$. In any k-bridge graphs with n vertices, the graph that the matching maximum root to get the smallest is 2-bridge graphs Cn(cycle), and the biggest one is (n-1)-bridge graph θn-1(0, 1, 1…, 1).

Key words: matching polynomial, matching maximum root, k-bridge graph

CLC Number: 

  • O157.5

Fig.1

k-fork tree Tk(a1, a2, …, ak) and k-bridge graph θk(a1, a2, …, ak)"

Fig.2

Graph θk, s(a1, a2, …, ak|b1, b2, …, bs) and (n-1)-bridge graph θn-1(0, 1, 1…, 1)"

Fig.3

Graph Gu, iPn"

Fig.4

Graphs Gv, 1Pn+1 and Ge, n"

Fig.5

Graphs G and G(e)"

1 GODSIL C D . Algebraic combinatorics[M]. New York: Chapman and Hall, 1993.
2 HEILMANN O J , LIEB E H . Theory of monomer-dimer systems[J]. Communications in Mathematical Physics, 1972, 25, 190- 232.
doi: 10.1007/BF01877590
3 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
4 HOSOYA H . Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J]. Bulletin of the Chemical Society of Japan, 1971, 44, 2332- 2339.
doi: 10.1246/bcsj.44.2332
5 GUTMAN I . A note on analogies between the characteristic and the matching polynomial of a graph[J]. Publications dc Linstitut Mathematique, 1982, 31 (45): 27- 31.
6 GODSIL C D . Hermite ploynomials and a duality relation for matching polynomials[J]. Combinatorica, 1981, 1 (3): 257- 262.
doi: 10.1007/BF02579331
7 FARRELL E J , WHITEHEAD E G , J r . Connections between the matching and chromatic polynomials[J]. International Journal of Mathematics and Mathematical Sciences, 1992, 15 (4): 757- 766.
doi: 10.1155/S016117129200098X
8 GODSIL C D , GUTMAN I . On the theory of the matching polynomials[J]. Journal of Graph Theory, 1981, 5 (2): 137- 144.
doi: 10.1002/jgt.3190050203
9 GODSIL C D , GUTMAN I . Some remarks on the matching polynomial and its zeros[J]. Croatica Chemica Acta, 1981, 54 (1): 53- 59.
10 FARRELL E J . An introduction to matching polynomial[J]. Journal of Combinatorial Theory, 1979, 27 (B): 75- 86.
11 MA H C , REN H Z . The new methods for cnstructing matching-equivalence graphs[J]. Disrete Mathematic, 2007, 307, 125- 131.
12 马海成. 匹配最大根小于2的图的匹配等价图类[J]. 系统科学与数学, 2003, 20 (3): 337- 342.
doi: 10.3969/j.issn.1000-0577.2003.03.007
MA Haicheng . The matching equivalent classes of graphs with the maximum matching root less than 2[J]. Journal of Systems Science and Mathematical Sciences, 2003, 20 (3): 337- 342.
doi: 10.3969/j.issn.1000-0577.2003.03.007
13 马海成. 匹配最大根小于等于2的图的匹配等价[J]. 数学学报, 2006, 49 (6): 1355- 1360.
doi: 10.3321/j.issn:0583-1431.2006.06.023
MA Haicheng . The matching equivalent classes of graphs with the maximum matching root less than or equal to 2[J]. Acta Mathematica Sinica, Chinese Series, 2006, 49 (6): 1355- 1360.
doi: 10.3321/j.issn:0583-1431.2006.06.023
14 马海成, 刘小花. θ-图的匹配能量和Hosoya指标排序[J]. 厦门大学学报(自然科学版), 2019, 58 (3): 391- 396.
MA Haicheng , LIU Xiaohua . The order of matching energy and Hosoya index of θ-graphs[J]. Journal of Xiamen University (Natural Science), 2019, 58 (3): 391- 396.
15 马海成, 李丹阳. 一类双圈图匹配多项式的最大根[J]. 广州大学学报(自然科学版), 2020, (1): 72- 77.
MA Haicheng , LI Danyang . The largest root of matching polynomials of a class of bicyclic graphs[J]. Journal of Guangzhou University(Natural Science Edition), 2020, (1): 72- 77.
16 CVETKOVIĆ D , DOOB M , SACHS H . Spectra of graphs: theory and application[M]. New York: Academic Press, 1980.
[1] GAO Shang, MA Hai-cheng. Class of matching equivalent graphs of K1∪P2∪In [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 26-36.
[2] XIE Cheng-ling, MA Hai-cheng. Matching equivalent classes of union graphs of two vertices and a path [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(1): 29-34.
[3] LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] QIN Zhao-yu,LIU Shi-lian*,YANG Yin-rong,LIU Fu-jun,LI Jian-yuan,SONG Chun-hua . Technology exploration for proteomics analysis in hepatopancreas of shrimp (Fenneropenaeus chinensis) with white spot syndrome[J]. J4, 2007, 42(7): 5 -08 .
[2] WU Dai-yong. Global attractivity of a nonlinear discrete Logistic model  with feedback control[J]. J4, 2013, 48(4): 114 -110 .
[3] ZHANG Fang-guo. Elliptic curves in cryptography: past, present and future…[J]. J4, 2013, 48(05): 1 -13 .
[4]

GAO Li-li,MA Xia,ZHAO Hong-fei,PEI Jia-wei,L〖AKU¨〗 Zhao-lin,ZHANG Bo-lin *

.

Physiological characteristics of Lactobacillus delbrueckii subsp. lactis
mutant strains with reduced H+-ATPase activity

[J]. J4, 2008, 43(7): 1 -09 .
[5] . Asymptotic behavior of  nonoscillatory solutions of second  order nonlinear differential equation with perturbation[J]. J4, 2009, 44(2): 19 -23 .
[6] DING Yue . H#-abundant semi-groups[J]. J4, 2008, 43(4): 55 -57 .
[7] MA Tong-yi1,2, LIU Chun-yan2. The generalized Shephard problem for Lp-mixed projection bodies and Minkowski-Funk transforms[J]. J4, 2012, 47(10): 21 -30 .
[8] SUN Lin, ZHENG Yu, YAO Juan. Robust non-fragile H∞ state feedback control for  uncertainty discrete singular systems[J]. J4, 2011, 46(1): 35 -41 .
[9] . Joint test in nonlinear regression models with AR(2) random errors[J]. J4, 2009, 44(7): 38 -43 .
[10] YU Wen-guang1, HUANG Yu-juan2. Ruin probability in an interfered multi-type risk model of a variable ruin limit[J]. J4, 2011, 46(3): 58 -62 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd