留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

2K1In的匹配等价图类

上一篇

下一篇

高尚, 马海成. 2K1∪In的匹配等价图类[J]. 西南大学学报(自然科学版), 2022, 44(2): 82-88. doi: 10.13718/j.cnki.xdzk.2022.02.010
引用本文: 高尚, 马海成. 2K1In的匹配等价图类[J]. 西南大学学报(自然科学版), 2022, 44(2): 82-88. doi: 10.13718/j.cnki.xdzk.2022.02.010
GAO Shang, MA Haicheng. The Class of Matching Equivalent Graphs of 2K1∪In[J]. Journal of Southwest University Natural Science Edition, 2022, 44(2): 82-88. doi: 10.13718/j.cnki.xdzk.2022.02.010
Citation: GAO Shang, MA Haicheng. The Class of Matching Equivalent Graphs of 2K1In[J]. Journal of Southwest University Natural Science Edition, 2022, 44(2): 82-88. doi: 10.13718/j.cnki.xdzk.2022.02.010

2K1In的匹配等价图类

  • 基金项目: 国家自然科学基金项目(11561056,11661066);青海省自然科学基金项目(2016-ZJ-914);青海民族大学研究生创新项目(07M2021001)
详细信息
    作者简介:

    高尚,硕士研究生,主要从事组合数学的研究 .

    通讯作者: 马海成,教授
  • 中图分类号: O157.5

The Class of Matching Equivalent Graphs of 2K1In

  • 摘要: 匹配多项式是一种组合计数多项式,与图的特征多项式、色多项式等有许多联系.对于无圈图,它等于特征多项式;对于一般图,它是该图路树的特征多项式的一个因式.每个图都有一个匹配多项式,但一个匹配多项式所确定的图不一定是唯一的,即不同构的图可能共享一个匹配多项式.如果一个图的匹配多项式唯一确定这个图,则称这个图是匹配唯一的.如果两个不同构的图拥有相同的匹配多项式,则称这两个图是匹配等价的.自提出匹配等价的概念以来,虽然已经有了许多研究,但对于给定的图G,想要完全刻画出它的匹配等价图类仍是十分困难的.本文在前人的研究基础之上,通过组合计数和数学归纳法计算了2K1In的匹配等价图的个数,并且利用组合分析的方法刻画了2K1In以及它的补图的匹配等价图类.
  • 加载中
  • [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] 马海成. K1In的匹配等价图类[J]. 兰州大学学报(自然科学版), 2005, 41(5): 127-130. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-XNND202202010.htm
  • 加载中
计量
  • 文章访问数:  871
  • HTML全文浏览数:  871
  • PDF下载数:  221
  • 施引文献:  0
出版历程
  • 收稿日期:  2021-01-19
  • 刊出日期:  2022-02-20

2K1In的匹配等价图类

    通讯作者: 马海成,教授
    作者简介: 高尚,硕士研究生,主要从事组合数学的研究
  • 青海民族大学 数学与统计学院,西宁 810007
基金项目:  国家自然科学基金项目(11561056,11661066);青海省自然科学基金项目(2016-ZJ-914);青海民族大学研究生创新项目(07M2021001)

摘要: 匹配多项式是一种组合计数多项式,与图的特征多项式、色多项式等有许多联系.对于无圈图,它等于特征多项式;对于一般图,它是该图路树的特征多项式的一个因式.每个图都有一个匹配多项式,但一个匹配多项式所确定的图不一定是唯一的,即不同构的图可能共享一个匹配多项式.如果一个图的匹配多项式唯一确定这个图,则称这个图是匹配唯一的.如果两个不同构的图拥有相同的匹配多项式,则称这两个图是匹配等价的.自提出匹配等价的概念以来,虽然已经有了许多研究,但对于给定的图G,想要完全刻画出它的匹配等价图类仍是十分困难的.本文在前人的研究基础之上,通过组合计数和数学归纳法计算了2K1In的匹配等价图的个数,并且利用组合分析的方法刻画了2K1In以及它的补图的匹配等价图类.

English Abstract

  • 开放科学(资源服务)标志码(OSID):

  • 本文仅考虑有限无向的简单图.设G是一个n阶图,G的一个匹配是指G的一个生成子图,它的每一个分支是孤立边或者孤立点,k-匹配是指其中有k条边的匹配.文献[1]定义了图G的匹配多项式为

    这里,p(Gk)是G的所有k-匹配的数目,并且约定p(G,0)=1.在文中为了方便,将μ(Gx)简记为μ(G).若图GHμ(Gx)=μ(Hx),则称图GH是匹配等价的,记为G~H.设G是一个图,以[G]表示图G的匹配等价图的集合,以σ(G)表示集合[G]的元的个数,即|[G]|.若σ(G)=1,称图G是匹配唯一的.

    K1表示一个孤立点.以Pn(n≥2)和Cn(n≥3)分别表示有n个点的路和圈.以Q(mn)表示圈Cm+1的一个点与Pn+1的一个端点粘接后得到的图.以Tijk表示只有1个3度点、3个1度点,且这个3度点到3个1度点的距离分别为ijk的树.以In(n≥6)表示路Pn-4的两个端点分别粘接一个P3的2度点后得到的图.以K1,4表示有5个点的星图.以G表示图G的补图.文中没有定义的概念和术语参见文献[2].

    匹配多项式是图的一种组合计数多项式,它带有图的许多信息,在物理和化学上有着极其重要的应用[3-8].文献[9-10]提供了一些与匹配多项式相关的研究结果.文献[11-12]虽然给出了匹配最大根小于等于2的图,以及这些图的补图匹配等价的一种规律,然而对于给定的图G,完全刻画集合[G]是很困难的.文献[13]确定了集合[Pm],[K1Cm],[Pm]和 $[\overline {{K_1} \cup {C_m}} ]$,文献[14]确定了集合[K1Pm]和 $[\overline {{K_1} \cup {P_m}} ]$,文献[15]确定了集合[2K1Pm]和 $[\overline {{2K_1} \cup {P_m}} ]$,文献[16]确定了集合[K1Im]和 $[\overline {{K_1} \cup {I_m}} ]$.在本文中,我们计算2K1In的匹配等价图的个数,并确定集合[2K1Im],进而确定集合 $[\overline {{2K_1} \cup {I_m}} ]$.

    文献[14]的定理1给出了K1Pm的匹配等价图类.为了方便,我们将与K1Pm的匹配等价的图的集合记为Φ1,则|Φ1|=σ(K1Pm).

    文献[15]的定理1和定理2给出了2K1Pm的匹配等价图类.通过观察我们发现,除了m+1=3×2n-1(n≥3)的情形外,2K1Pm的每一个匹配等价图包含且仅包含一个路分支.而当m+1=3×2n-1(n≥3)时,2K1Pm的匹配等价图中含有Q(2,1)分支的等价图是:Q(2,1)∪HHΔ4,其中的每一个H有且恰有两个不同的路分支.用Φ2表示2K1Pm的每一个匹配等价图中删去一条路分支后得到的图的集合.于是

    为了方便,本文用σ(GH)表示图G的所有匹配等价图中含有分支H的等价图的个数.

    引理1  (ⅰ)  若m+1=3×2n-1对某个正整数n成立,则

    (ⅱ) 若m+1的最大奇因数不是3,则σ(3K1PmP2)=0.

      (ⅰ)  H~3K1PmH1H的连通分支,使得

    n用数学归纳法.当n=1时,结论明显.当n=2时,由文献[16]的引理2,3和4得,H1=P5C3T1,1,1,相应地,H2~3K1,3K1P2,2K1P2,则

    n=3时,由文献[16]的引理2,3和4得,H1=P11C6T1,1,4Q(2,1),T1,2,2,相应地,H2~3K1,3K1P5,2K1P5,2K1P3P5,2K1P3C3,由文献[16]的引理10得

    n≥4时,由文献[16]的引理2,3和4得,H1=PmCm2+1T1,1,m2-1(m2+1=3×2n-2),相应地,H2~3K1,3K1Pm2,2K1Pm2,由文献[16]的引理10得

    (ⅱ)  按m+1的最大奇因数是1,9,15或其他奇数分以下(a)-(d) 4种情形.

    H~3K1PmH1H的连通分支,使得

    (a) m+1=2n+1.当n=1时,σ(3K1P3P2)=0,假设结论对m2+1=2n成立,且对n用数学归纳法,H1=PmCm2+1T1,1,m2-1,相应地,H2~3K1,3K1Pm2,2K1Pm2,则

    (b) m+1=9×2n-1.当n=1时,σ(3K1P8P2)=0.当n=2时,H1=P17C9T1,1,7T1,2,3,相应地,H2~3K1,3K1P8,2K1P8,2K1C3P8,则

    假设结论对m2+1=9×2n-2成立,且对n用数学归纳法,H1=PmCm2+1T1,1,m2-1,相应地,H2~3K1,3K1Pm2,2K1Pm2,则

    (c) m+1=15×2n-1.当n=1时,σ(3K1P14P2)=0.当n=2时,H1=P29C15T1,1,13T1,2,4,相应地,H2~3K1,3K1P14,2K1P14,2K1C3P14,则

    假设结论对m2+1=15×2n-2成立,且对n用数学归纳法,H1=PmCm2+1T1,1,m2-1,相应地,H2~3K1,3K1Pm2,2K1Pm2,则

    (d) m+1=2n-1(2k+1),k(≠0,1,4,7)为整数.当n=1时,σ(3K1P2kP2)=0.假设结论对m2+1=2n-2(2k+1)成立,且对n用数学归纳法,H1=PmCm2+1T1,1,m2-1,相应地,H2~3K1,3K1Pm2,2K1Pm2,则

    引理2  若m+1=3×2n-1对某个正整数n成立,则3K1Pm的匹配等价图中含有分支P2的图是下面的图:

    (ⅰ)  n=1时,3K1P2

    (ⅱ)  n=2时,3K1P2C3,2K1P2T1,1,1

    (ⅲ)  n≥3时,3K1P2C3C6C12∪…∪C3×2n-2

      由文献[16]的引理2,3和4得,这些图均等价于3K1Pm,且含有分支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)$张图.以及含有两条路分支P2P3的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得,图的个数也等于σ(3K1PmP2).

    引理3  若m≥2是整数,σ(3K1Pm,2P2)=0,σ(3K1PmP2P4)=0.

      由引理1和引理2,结果显然.

    为了方便,用Φ3表示3K1Pm的含有分支P2的所有匹配等价图中删去P2后得到的图的集合,即引理2中的每张图删去P2后得到的图的集合,则|Φ3|=σ(3K1PmP2).用Φ4表示3K1Pm的含有分支P2P3的所有匹配等价图中删去P2P3后得到的图的集合,即引理2中的每张图删去P2P3后得到的图的集合,则|Φ4|=σ(3K1PmP2P3).

    为了找到2K1Im(m≥6)的匹配等价图类,按m-3所含最大奇因数是1,3,9,15或其他奇数分为5类.

    定理1  (ⅰ) 若m-3=2n+1对某个正整数n成立,则

    此时2K1Im的匹配等价图分为两类:含I-形分支的是ItH2H2Φ2,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + n$张;含K1,4-形分支的是K1,4H2H2Φ1,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) $张.

    (ⅱ)  若m-3=2n-1(2k+1)对某对正整数nk(≠1,4,7)成立,则

    此时2K1Im的匹配等价图分为两类:含I-形分支的是ItH2H2Φ2,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + n$张;含K1,4-形分支的是K1,4H2H2Φ1,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) $张.

    (ⅲ) 若m-3=9×2n-1对某个正整数n成立,则

    此时2K1Im的匹配等价图分为两类:含I-形分支的是ItH2H2Φ2,当n=1时有1张图,当n≥2时,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + 2n$张;含K1,4-形分支的是K1,4H2H2Φ1,当n=1时有1张图,当n≥2时,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) +1$张.

    (ⅳ)  若m-3=15×2n-1对某个正整数n成立,则

    此时2K1Im的匹配等价图分为两类:含I-形分支的是ItH2H2Φ2,当n=1时有1张图,当n≥2时,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 3 \end{array}} \right) + 2n + 1$张;含K1,4-形分支的是K1,4H2H2Φ1,当n=1时有1张图,当n≥2时,这样的图共有 $\left( {\begin{array}{*{20}{c}} {n + 1}\\ 2 \end{array}} \right) +1$张.

    (ⅴ)  若m-3=3×2n-1对某个正整数n成立,则

    此时2K1Im的匹配等价图分为5类:含I-形分支的是ItH2H2Φ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,4H2H2Φ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)∪H2H2Φ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)∪H2H2Φ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,3H2H2Φ4,当n=1时有0张图,当n=2时有0张图,当n≥3时有 $\left( {\begin{array}{*{20}{c}} {n - 1}\\ 2 \end{array}} \right) +1$张图.

      设H~2K1Im,由M1(H)=2及文献[16]的引理2(2)知,H必有一连通分支H1Ω2H=H1H2.

    (ⅰ)  分以下3种情形:

    (a) 若H1=It(t≥6),则

    两边并Pm-4,利用文献[16]的引理13(8)得

    由文献[15]的定理1和定理2知,这样的H2Φ2.

    (b) 若H1=K1,4,则

    两边并Pm-4P2,利用文献[16]的引理13(7),(8)得

    由文献[14]的定理1知,这样的H2Φ1.

    (c) 若H1=Q(2,2),Q(3,1)(~Q(2,2)),T2,2,2(~P2Q(2,2)),T1,3,3(~P3Q(2,2)),T1,2,5(~P4Q(2,2)),均可设

    两边并K1Pm-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,结论显然.

参考文献 (16)

目录

/

返回文章
返回