-
开放科学(资源服务)标志码(OSID):
-
本文仅考虑有限无向的简单图.设G是一个n阶图,G的一个匹配是指G的一个生成子图,它的每一个分支是孤立边或者孤立点,k-匹配是指其中有k条边的匹配.文献[1]定义了图G的匹配多项式为
这里,p(G,k)是G的所有k-匹配的数目,并且约定p(G,0)=1.在文中为了方便,将μ(G,x)简记为μ(G).若图G和H有μ(G,x)=μ(H,x),则称图G和H是匹配等价的,记为G~H.设G是一个图,以[G]表示图G的匹配等价图的集合,以σ(G)表示集合[G]的元的个数,即|[G]|.若σ(G)=1,称图G是匹配唯一的.
以K1表示一个孤立点.以Pn(n≥2)和Cn(n≥3)分别表示有n个点的路和圈.以Q(m,n)表示圈Cm+1的一个点与Pn+1的一个端点粘接后得到的图.以Ti,j,k表示只有1个3度点、3个1度点,且这个3度点到3个1度点的距离分别为i,j,k的树.以In(n≥6)表示路Pn-4的两个端点分别粘接一个P3的2度点后得到的图.以K1,4表示有5个点的星图.以G表示图G的补图.文中没有定义的概念和术语参见文献[2].
匹配多项式是图的一种组合计数多项式,它带有图的许多信息,在物理和化学上有着极其重要的应用[3-8].文献[9-10]提供了一些与匹配多项式相关的研究结果.文献[11-12]虽然给出了匹配最大根小于等于2的图,以及这些图的补图匹配等价的一种规律,然而对于给定的图G,完全刻画集合[G]是很困难的.文献[13]确定了集合[Pm],[K1∪Cm],[Pm]和
$[\overline {{K_1} \cup {C_m}} ]$ ,文献[14]确定了集合[K1∪Pm]和$[\overline {{K_1} \cup {P_m}} ]$ ,文献[15]确定了集合[2K1∪Pm]和$[\overline {{2K_1} \cup {P_m}} ]$ ,文献[16]确定了集合[K1∪Im]和$[\overline {{K_1} \cup {I_m}} ]$ .在本文中,我们计算2K1∪In的匹配等价图的个数,并确定集合[2K1∪Im],进而确定集合$[\overline {{2K_1} \cup {I_m}} ]$ .文献[14]的定理1给出了K1∪Pm的匹配等价图类.为了方便,我们将与K1∪Pm的匹配等价的图的集合记为Φ1,则|Φ1|=σ(K1∪Pm).
文献[15]的定理1和定理2给出了2K1∪Pm的匹配等价图类.通过观察我们发现,除了m+1=3×2n-1(n≥3)的情形外,2K1∪Pm的每一个匹配等价图包含且仅包含一个路分支.而当m+1=3×2n-1(n≥3)时,2K1∪Pm的匹配等价图中含有Q(2,1)分支的等价图是:Q(2,1)∪H,H∈Δ4,其中的每一个H有且恰有两个不同的路分支.用Φ2表示2K1∪Pm的每一个匹配等价图中删去一条路分支后得到的图的集合.于是
为了方便,本文用σ(G,H)表示图G的所有匹配等价图中含有分支H的等价图的个数.
引理1 (ⅰ) 若m+1=3×2n-1对某个正整数n成立,则
(ⅱ) 若m+1的最大奇因数不是3,则σ(3K1∪Pm,P2)=0.
证 (ⅰ) H~3K1∪Pm,H1是H的连通分支,使得
对n用数学归纳法.当n=1时,结论明显.当n=2时,由文献[16]的引理2,3和4得,H1=P5,C3,T1,1,1,相应地,H2~3K1,3K1∪P2,2K1∪P2,则
当n=3时,由文献[16]的引理2,3和4得,H1=P11,C6,T1,1,4,Q(2,1),T1,2,2,相应地,H2~3K1,3K1∪P5,2K1∪P5,2K1∪P3∪P5,2K1∪P3∪C3,由文献[16]的引理10得
当n≥4时,由文献[16]的引理2,3和4得,H1=Pm,Cm2+1,T1,1,m2-1(m2+1=3×2n-2),相应地,H2~3K1,3K1∪Pm2,2K1∪Pm2,由文献[16]的引理10得
(ⅱ) 按m+1的最大奇因数是1,9,15或其他奇数分以下(a)-(d) 4种情形.
设H~3K1∪Pm,H1是H的连通分支,使得
(a) m+1=2n+1.当n=1时,σ(3K1∪P3,P2)=0,假设结论对m2+1=2n成立,且对n用数学归纳法,H1=Pm,Cm2+1,T1,1,m2-1,相应地,H2~3K1,3K1∪Pm2,2K1∪Pm2,则
(b) m+1=9×2n-1.当n=1时,σ(3K1∪P8,P2)=0.当n=2时,H1=P17,C9,T1,1,7,T1,2,3,相应地,H2~3K1,3K1∪P8,2K1∪P8,2K1∪C3∪P8,则
假设结论对m2+1=9×2n-2成立,且对n用数学归纳法,H1=Pm,Cm2+1,T1,1,m2-1,相应地,H2~3K1,3K1∪Pm2,2K1∪Pm2,则
(c) m+1=15×2n-1.当n=1时,σ(3K1∪P14,P2)=0.当n=2时,H1=P29,C15,T1,1,13,T1,2,4,相应地,H2~3K1,3K1∪P14,2K1∪P14,2K1∪C3∪P14,则
假设结论对m2+1=15×2n-2成立,且对n用数学归纳法,H1=Pm,Cm2+1,T1,1,m2-1,相应地,H2~3K1,3K1∪Pm2,2K1∪Pm2,则
(d) m+1=2n-1(2k+1),k(≠0,1,4,7)为整数.当n=1时,σ(3K1∪P2k,P2)=0.假设结论对m2+1=2n-2(2k+1)成立,且对n用数学归纳法,H1=Pm,Cm2+1,T1,1,m2-1,相应地,H2~3K1,3K1∪Pm2,2K1∪Pm2,则
引理2 若m+1=3×2n-1对某个正整数n成立,则3K1∪Pm的匹配等价图中含有分支P2的图是下面的图:
(ⅰ) n=1时,3K1∪P2;
(ⅱ) n=2时,3K1∪P2∪C3,2K1∪P2∪T1,1,1;
(ⅲ) n≥3时,3K1∪P2∪C3∪C6∪C12∪…∪C3×2n-2;
证 由文献[16]的引理2,3和4得,这些图均等价于3K1∪Pm,且含有分支P2.对n≥3,它们可以分为仅含一条路分支P2的4类:不含T-形树分支的1张图;含1个T-形树分支的n-1张图;含2个T-形树分支的
$\left( {\begin{array}{*{20}{c}} {n - 1}\\ 2 \end{array}} \right)$ 张图;含3个T-形树分支的$\left( {\begin{array}{*{20}{c}} {n - 1}\\ 3 \end{array}} \right)$ 张图.以及含有两条路分支P2∪P3的3类:不含T-形树分支的1张图;含1个T-形树分支的n-2张图;含2个T-形树分支的$\left( {\begin{array}{*{20}{c}} {n - 2}\\ 2 \end{array}} \right)$ 张图.共$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right)+2$ 张图.由引理1得,图的个数也等于σ(3K1∪Pm,P2).引理3 若m≥2是整数,σ(3K1∪Pm,2P2)=0,σ(3K1∪Pm,P2∪P4)=0.
证 由引理1和引理2,结果显然.
为了方便,用Φ3表示3K1∪Pm的含有分支P2的所有匹配等价图中删去P2后得到的图的集合,即引理2中的每张图删去P2后得到的图的集合,则|Φ3|=σ(3K1∪Pm,P2).用Φ4表示3K1∪Pm的含有分支P2∪P3的所有匹配等价图中删去P2∪P3后得到的图的集合,即引理2中的每张图删去P2∪P3后得到的图的集合,则|Φ4|=σ(3K1∪Pm,P2∪P3).
为了找到2K1∪Im(m≥6)的匹配等价图类,按m-3所含最大奇因数是1,3,9,15或其他奇数分为5类.
定理1 (ⅰ) 若m-3=2n+1对某个正整数n成立,则
此时2K1∪Im的匹配等价图分为两类:含I-形分支的是It∪H2,H2∈Φ2,这样的图共有
$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + n$ 张;含K1,4-形分支的是K1,4∪H2,H2∈Φ1,这样的图共有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) $ 张.(ⅱ) 若m-3=2n-1(2k+1)对某对正整数n,k(≠1,4,7)成立,则
此时2K1∪Im的匹配等价图分为两类:含I-形分支的是It∪H2,H2∈Φ2,这样的图共有
$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + n$ 张;含K1,4-形分支的是K1,4∪H2,H2∈Φ1,这样的图共有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) $ 张.(ⅲ) 若m-3=9×2n-1对某个正整数n成立,则
此时2K1∪Im的匹配等价图分为两类:含I-形分支的是It∪H2,H2∈Φ2,当n=1时有1张图,当n≥2时,这样的图共有
$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + 2n$ 张;含K1,4-形分支的是K1,4∪H2,H2∈Φ1,当n=1时有1张图,当n≥2时,这样的图共有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) +1$ 张.(ⅳ) 若m-3=15×2n-1对某个正整数n成立,则
此时2K1∪Im的匹配等价图分为两类:含I-形分支的是It∪H2,H2∈Φ2,当n=1时有1张图,当n≥2时,这样的图共有
$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + 2n + 1$ 张;含K1,4-形分支的是K1,4∪H2,H2∈Φ1,当n=1时有1张图,当n≥2时,这样的图共有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) +1$ 张.(ⅴ) 若m-3=3×2n-1对某个正整数n成立,则
此时2K1∪Im的匹配等价图分为5类:含I-形分支的是It∪H2,H2∈Φ2,当n=1时有1张图,当n=2时有3张图,当n≥3时有
$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + 6n - 7$ 张图;含K1,4-形分支的是K1,4∪H2,H2∈Φ1,当n=1时有1张图,当n=2时有3张图,当n≥3时有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right)+3 $ 张图;含Q(2,2)-形分支的是Q(2,2)∪H2,H2∈Φ3,当n=1时有1张图,当n=2时有2张图,当n≥3时有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) +2$ 张图;含Q(3,1)-形分支的是Q(3,1)∪H2,H2∈Φ3,当n=1时有1张图,当n=2时有2张图,当n≥3时有$\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) +2$ 张图;含T1,3,3-形分支的是T1,3,3∪H2,H2∈Φ4,当n=1时有0张图,当n=2时有0张图,当n≥3时有$\left( {\begin{array}{*{20}{c}} {n - 1}\\ 2 \end{array}} \right) +1$ 张图.证 设H~2K1∪Im,由M1(H)=2及文献[16]的引理2(2)知,H必有一连通分支H1∈Ω2,H=H1∪H2.
(ⅰ) 分以下3种情形:
(a) 若H1=It(t≥6),则
两边并Pm-4,利用文献[16]的引理13(8)得
则
由文献[15]的定理1和定理2知,这样的H2∈Φ2.
(b) 若H1=K1,4,则
两边并Pm-4∪P2,利用文献[16]的引理13(7),(8)得
则
由文献[14]的定理1知,这样的H2∈Φ1.
(c) 若H1=Q(2,2),Q(3,1)(~Q(2,2)),T2,2,2(~P2∪Q(2,2)),T1,3,3(~P3∪Q(2,2)),T1,2,5(~P4∪Q(2,2)),均可设
两边并K1∪Pm-4,利用文献[16]的引理13(3),(8)得
则
由引理1(ⅱ)知,这样的H2不存在.
(ⅱ)-(ⅳ)的证明与(ⅰ)类似,略.
(ⅴ) 分以下7种情形:
(a) 若H1=It(t≥6),与(ⅰ)的情形(a)类似,这样的H2∈Φ2.
(b) 若H1=K1,4,与(ⅰ)的情形(b)类似,这样的H2∈Φ1.
(c) 若H1=Q(2,2),则
与(ⅰ)的情形(c)类似,可得到
由引理2知,这样的H2∈Φ3.
(d) 若H1=Q(3,1),由Q(3,1)~Q(2,2),与情形(c)类似,这样的H2∈Φ3.
(e) 若H1=T1,3,3,由文献[16]的引理13(5)得
与(ⅰ)的情形(c)类似,可得到
由引理1和引理2知:当n≤2时,这样的H2不存在;当n≥3时,这样的H2∈Φ4.
(f) 若H1=T2,2,2.由文献[16]的引理13(4)得
与(ⅰ)的情形(c)类似,可得到
由引理3知,这样的H2不存在.
(g) 若H1=T1,2,5,由文献[16]的引理13(6)得
与(ⅰ)的情形(c)类似,可得到
由引理3知,这样的H2不存在.
推论1 对于定理1所述的每一种情形,
$\overline {2{K_1} \cup {I_m}} $ 的匹配等价图是定理1所述的那些图的补图.证 由文献[16]的引理14,结论显然.
The Class of Matching Equivalent Graphs of 2K1∪In
-
摘要: 匹配多项式是一种组合计数多项式,与图的特征多项式、色多项式等有许多联系.对于无圈图,它等于特征多项式;对于一般图,它是该图路树的特征多项式的一个因式.每个图都有一个匹配多项式,但一个匹配多项式所确定的图不一定是唯一的,即不同构的图可能共享一个匹配多项式.如果一个图的匹配多项式唯一确定这个图,则称这个图是匹配唯一的.如果两个不同构的图拥有相同的匹配多项式,则称这两个图是匹配等价的.自提出匹配等价的概念以来,虽然已经有了许多研究,但对于给定的图G,想要完全刻画出它的匹配等价图类仍是十分困难的.本文在前人的研究基础之上,通过组合计数和数学归纳法计算了2K1∪In的匹配等价图的个数,并且利用组合分析的方法刻画了2K1∪In以及它的补图的匹配等价图类.Abstract: The matching polynomial is a kind of combinatorial counting polynomial, which has many relations with the characteristic polynomial and the chromatic polynomial of the graph.For a acyclic graph, it is equal to the characteristic polynomial; for a general graph, it is a factor of the characteristic polynomial of the path tree of the graph.Every graph has a matching polynomial, but the graph determined by a matching polynomial is not necessarily unique, that is, different graphs may share the same matching polynomial.If the matching polynomial of a graph uniquely determines the graph, then the graph is said to be matching unique.If two graphs have the same matching polynomial, then the two graphs are said to be matching equivalent.Since the concept of matching equivalence as proposed, it is very difficult to characterize the class of matching equivalent graphs for a given graph G.On the basis of previous studies, the number of matching equivalent graphs of 2K1∪In calculated by using combination counting and mathematical induction, and the classes of matching equivalent graphs of 2K1∪In and its complement graphs recharacterized by using combination analysis.
-
Key words:
- matching polynomial /
- matching equivalence /
- matching unique .
-
-
[1] GODSIL C D, GUTMAN I. On the Theory of the Matching Polynomial [J]. Journal of Graph Theory, 1981, 5(2): 137-144. doi: 10.1002/jgt.3190050203 [2] BONDY J A, MURTY U S R. Graph Theory [M]. New York: Springer-Verlag, 2008. [3] KUNZ H. Location of the Zeros of the Partition Function for Some Classical Lattice Systems [J]. Physis Letters A, 1970, 32(5): 311-312. doi: 10.1016/0375-9601(70)90520-7 [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(9): 2332-2339. doi: 10.1246/bcsj.44.2332 [5] FARRELL E J. An Introduction to Matching Polynomials [J]. Journal of Combinatorial Theory (Series B), 1979, 27(1): 75-86. doi: 10.1016/0095-8956(79)90070-4 [6] doi: http://www.onacademic.com/detail/journal_1000034341481510_6820.html JERRUM M. Two-Dimensional Monomer-Dimer Systems Are Computationally Intractable [J]. Journal of Statistical Physis, 1987, 48(1/2): 121-134. [7] DONG F M. A New Expression for Matching Polynomials [J]. Discrete Mathematics, 2012, 312(4): 803-807. doi: 10.1016/j.disc.2011.11.019 [8] GUTMAN I, WAGNER S. The Matching Energy of a Graph [J]. Discrete Applied Mathematics, 2012, 160(15): 2177-2187. doi: 10.1016/j.dam.2012.06.001 [9] 唐保祥, 任韩. 2类图完美对集数的计算公式[J]. 西南师范大学学报(自然科学版), 2020, 45(10): 13-15. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-XNZK202010003.htm [10] 刘寅, 王鼎. 完全图K2n的边传递循环覆盖[J]. 西南大学学报(自然科学版), 2021, 43(2): 90-94. doi: http://xbgjxt.swu.edu.cn/article/doi/10.13718/j.cnki.xdzk.2021.02.012 [11] 马海成. 匹配最大根小于2的图的匹配等价类[J]. 系统科学与数学, 2003, 23(3): 337-342. doi: 10.3969/j.issn.1000-0577.2003.03.007 [12] 马海成. 匹配最大根小于等于2的图的匹配等价[J]. 数学学报, 2006, 49(6): 1355-1360. doi: 10.3321/j.issn:0583-1431.2006.06.023 [13] 马海成. 两类图的匹配等价类[J]. 数学研究, 2000, 33(2): 218-222. doi: 10.3969/j.issn.1006-6837.2000.02.019 [14] 马海成. 点并路的匹配等价图类[J]. 青海师范大学学报(自然科学版), 2003, 19(1): 6-8, 13. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-QHSD200301002.htm [15] 解承玲, 马海成. 两个点并路的匹配等价图类[J]. 山东大学学报(理学版), 2021, 56(1): 29-34. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-SDDX202101005.htm [16] 马海成. K1∪In的匹配等价图类[J]. 兰州大学学报(自然科学版), 2005, 41(5): 127-130. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-XNND202202010.htm -
计量
- 文章访问数: 869
- HTML全文浏览数: 869
- PDF下载数: 221
- 施引文献: 0