小直径匹配整图
Matching Integral Graphs withSmall-Diameter
DOI: 10.12677/PM.2025.157212, PDF,    科研立项经费支持
作者: 马仰光：青海民族大学数学与统计学院，青海 西宁
关键词: 匹配多项式；整图；路树；Matching Polynomial； Integral Graphs； Path-Trees
摘要: 令G是n个顶点的图。匹配整图表示的是匹配多项式的根都是整数的图。本文运用路树的相关概念，通过将树的一些分支进行路径收缩得到带有圈的匹配整图，利用这种方法构造了一些直径为4,5,6的匹配整图。
Abstract: Let G be a graph with n vertices. Matching integral graphs are defined as graphs where all roots of the matching polynomial are integers. In this paper, by applying concepts related to path-trees and contracting some branches of a tree into paths, we derive matching integral graphs that contain cycles.Using this approach, we construct several matching integral graphs with diameters 4, 5, and 6.
文章引用：马仰光. 小直径匹配整图[J]. 理论数学, 2025, 15(7): 99-107. https://doi.org/10.12677/PM.2025.157212

参考文献

[1] 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
[2] Heilmann, O.J. and Lieb, E.H. (1972) Theory of Monomer-Dimer Systems. Communications in Mathematical Physics, 25, 190-232.
https://doi.org/10.1007/bf01877590
[3] Farrell, E.J. (1979) An Introduction to Matching Polynomials. Journal of Combinatorial Theory, Series B, 27, 75-86.
https://doi.org/10.1016/0095-8956(79)90070-4
[4] Godsil, C.D. and Gutman, I. (1981) On the Theory of the Matching Polynomial. Journal of Graph Theory, 5, 137-144.
https://doi.org/10.1002/jgt.3190050203
[5] Godsil, C.D. (1981) Hermite Polynomials and a Duality Relation for Matchings Polynomials. Combinatorica, 1, 257-262.
https://doi.org/10.1007/bf02579331
[6] Jerrum, M. (1987) Two-Dimensional Monomer-Dimer Systems Are Computationally Intractable. Journal of Statistical Physics, 48, 121-134.
https://doi.org/10.1007/bf01010403
[7] Lovasz, L. and Plummer, M. (2009) Matching Theory. American Mathematical Society.
https://doi.org/10.1090/chel/367
[8] Li, X.L. and Lin, G.N. (1988) On Integral Trees Problems. Chinese Science Bulletin, 33, 802- 806 (In English). (Or Kexue Tongbao (Chinese), Vol. 32 (1987), No. 11, 813-816 (In Chinese))
[9] Brouwer, A.E. (2008) Small Integral Trees. The Electronic Journal of Combinatorics, 15, Article No. N1. https://doi.org/10.37236/876
[10] Wang, L. (2005) Integral Trees and Integral Graphs. PhD Thesis, University of Twente.

为你推荐