k-桥图匹配最大根的极值

doi:10.6040/j.issn.1671-9352.0.2023.041

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (6): 19-24.doi: 10.6040/j.issn.1671-9352.0.2023.041

k-桥图匹配最大根的极值

马海成(),攸晓杰

青海民族大学数学与统计学院, 青海西宁 810007

收稿日期:2023-10-30 出版日期:2024-06-20 发布日期:2024-06-17
作者简介:马海成(1965—), 男, 教授, 博士, 研究方向为代数图论. E-mail: qhmymhc@163.com
基金资助:
国家自然科学基金资助项目(11561056);青海省自然科学基金资助项目(2022-ZJ-924)

Extremum of the matching maximum root of k-bridge graphs

Haicheng MA(),Xiaojie YOU

School of Mathematics and Statistics, Qinghai Minzu University, Xining 810007, Qinghai, China

Received:2023-10-30 Online:2024-06-20 Published:2024-06-17

摘要/Abstract

摘要：

设G是有n个点的图, μ(G, x)表示图G的匹配多项式, M₁(G)表示多项式μ(G, x)的最大根, 称为匹配最大根。把k条路P_a₁+2, P_a₂+2, …, P_{a_k+2}的左右2个端点分别黏结成2个点后得到的图称为k-桥图, 记为θ_k(a₁, a₂, …, a_k)。有n个点且每一条路上的点数几乎相等的k-桥图记为θ_k^* (n)。证明了: 在n个点的k-桥图中匹配最大根取得最小的图是$\theta_k(0, \overbrace{1, 1 \cdots, 1}^{k-2}, n-k)$; 在n个点的任意k-桥图中匹配最大根取得最小的图是2-桥图(圈)C_n, 最大的图是(n-1)-桥图θ_n-1(0, 1, 1…, 1)。

关键词: 匹配多项式, 匹配最大根, k-桥图

Abstract:

Let G be a graph with n vertices, and μ(G, x) denote the matching polynomial of graph G, M₁(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 P_a₁+2, P_a₂+2, …, P_{a_k+2}, respectively, the resulting graph is called the k-bridge graphs, denoted by θ_k(a₁, a₂, …, a_k). 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 C_n(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

中图分类号:

O157.5

马海成,攸晓杰. k-桥图匹配最大根的极值[J]. 《山东大学学报(理学版)》, 2024, 59(6): 19-24.

Haicheng MA,Xiaojie YOU. Extremum of the matching maximum root of k-bridge graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 19-24.

图/表 5

图1

图2

图3

图4

图5

参考文献 16

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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

[1]	高尚,马海成. K₁∪P₂∪I_n的匹配等价图类[J]. 《山东大学学报(理学版)》, 2022, 57(11): 26-36.
[2]	解承玲, 马海成. 两个点并路的匹配等价图类[J]. 《山东大学学报(理学版)》, 2021, 56(1): 29-34.
[3]	刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.

k-桥图匹配最大根的极值

Extremum of the matching maximum root of k-bridge graphs

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 16

相关文章 3

多维度评价

本文评价

推荐阅读 10