On Calculation Formula for Perfect Matching Number of Two Types of Graphs

Bao-xiang TANG; Han REN

doi:10.13718/j.cnki.xsxb.2020.10.003

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

The perfect matchings of graphs N_mn and 3-nK_{3, 3} have been classified according to the edge associated with a vertex, and the recurrence relationship of the number of perfect matchings of each type been obtained, and then the sum and nested recursion methods been used to give the counting formulas for the different perfect matchings in graphs N_mn and 3-nK_{3, 3} are 2ⁿ and 6ⁿ.

HTML

图的完美对集的计数问题的研究有重要的理论价值和现实意义^[1-3].此问题已经被证实是NP-困难问题.分类嵌套递推的方法是求解许多类图完美对集数的一种非常有效的方法^[4-10].本文构造了2类新的N_mn和3-nK_3，3，用分类嵌套递推的方法求出了图N_mn和3-nK_3，3不同完美对集的计数公式.

定义1   如果图G有1-正则生成子图P，那么就称这个生成子图P为图G的完美对集.

定义2   设图G是有完美对集的图，如果图G的两个完美对集P₁和P₂中有一条边不同，那么就称P₁和P₂是G的两个不同的完美对集.

定义3   设长度为2m的圈C_mⁱ的顶点集合为V(C_mⁱ)={u_i1，u_i2，…，u_im，v_i1，v_i2，…，v_im}(i=1，2，…，n)，把圈C_mⁱ的顶点v_i1，v_i2，…，v_im与圈C_mⁱ⁺¹的顶点u_i+1，1，u_i+1，2，…，u_i+1，m(i=1，2，…，n－1)连接成圈v_i1u_i+1，2v_i3u_i+1，4v_i5…v_i，m－1u_i+1，mv_imu_i+1，m－1v_i，m－2…u_i+1，3v_i2u_i+1，1v_i1(i=1，2，…，n－1)，这样产生的图记为N_mn，见图 1.

定义4   设完全偶图K_3，3ⁱ的顶点集合为V(K_3，3ⁱ)={u_i1，u_i2，u_i3，v_i1，v_i2，v_i3}(i=1，2，…，n)，把圈K_3，3ⁱ的顶点v_i1，v_i2，v_i3分别与圈K_3，3ⁱ⁺¹的顶点u_i+1，1，u_i+1，2，u_i+1，3 (i=1，2，…，n－1)各连接一条边，这样产生的图记为3-nK_3，3，见图 2.

定理1   设图N_mn的完美对集数为δ(m，n)，则δ(n)=2ⁿ.

证   因为图N_mn的每个圈C_mⁱ:v_i1u_i2v_i3u_i4v_i5…v_i，m－1u_imv_imu_i，m－1v_i，m－2…u_i3v_i2u_i1v_i1恰有2个完美对集(i=1，2，…，n)，每个圈取定一个完美对集，就形成图N_mn的一个完美对集.因此，由乘法原理可知，图N_mn至少有2ⁿ个不同的完美对集.下面证明图N_mn只有2ⁿ个不同的完美对集.

设P是图N_mn的完美对集的集合，对于集合P中的任何一个完美匹配P_i，P_i一定要饱和顶点u₁₁.与顶点u₁₁关联的边只有2条，所以集合P可划分为2类:P₁，P₂.设u₁₁v₁₁∈P₁，u₁₁v₁₂∈P₂，则$ P_{1} \cap P_{2}=\emptyset, P=P_{1} \cup P_{2}$，故δ(m，n)=|P|=|P₁|+|P₂|.

因为u₁₁v₁₁∈P₁，所以当m是偶数时，边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃，u₁₄v₁₅，v₁₄u₁₅，…，u_1，m－2v_1，m－1，v_1，m－2u_1，m－1，u_1mv_1m都属于P₁; 当m是奇数时，边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃，u₁₄v₁₅，v₁₄u₁₅，…，u_1，m－1v_1m，v_1，m－1u_1m都属于P₁.由δ(m，n)的定义可知，|P₁|=δ(m，n－1).

因为u₁₁v₁₂∈P₂，所以当m是偶数时，边v₁₁u₁₂，u₁₃v₁₄，v₁₃u₁₄，u₁₅v₁₆，v₁₅u₁₆，…，u_1，m－2v_1，m，v_1，m－1u_1，m都属于P₂; 当m是奇数时，边v₁₁u₁₂，u₁₃v₁₄，v₁₃u₁₄，u₁₅v₁₆，v₁₅u₁₆，…，u_1，m－2v_1，m－1，v_1，m－2u_1，m－1，u_1mv_1m都属于P₂.由δ(m，n)的定义可知，|P₂|=δ(m，n－1).

因此，δ(m，n)=|P|=2δ(m，n－1)=…=2^n－1δ(m，1)=2ⁿ.

定理2   设图 3-nK_3，3的完美对集数为γ(n)，则γ(n)=6ⁿ.

证  图 3-nK_3，3存在完美对集是明显的.设图 3-nK_3，3的完美对集的集合为S，对于集合S中的任何一个完美匹配S_i，S_i一定要饱和顶点u₁₁.与顶点u₁₁关联的边有3条，所以集合S可划分为3类:S₁，S₂，S₃.设u₁₁v₁₁∈S₁，u₁₁v₁₂∈S₂，u₁₁v₁₃∈S₃，则S_i∩S_j=(1≤i < j≤3)，S=S₁∪S₂∪S₃.故γ(n)=|S|=|S₁|+|S₂|+|S₃|.

S₁划分为两类. S₁中含边u₁₁v₁₁，u₁₂v₁₂，u₁₃v₁₃的完美对集集合记为S₁¹; S₁中含边u₁₁v₁₁，u₁₂v₁₃，v₁₂u₁₃的完美对集集合记为S₁².由γ(n)的定义可知

因此，有

S₂划分为两类. S₂中含边u₁₁v₁₂，v₁₁u₁₂，u₁₃v₁₃的完美对集集合记为S₂¹; S₂中含边u₁₁v₁₂，v₁₁u₁₃，u₁₂v₁₃的完美对集集合记为S₂².由γ(n)的定义可知

因此，有

S₃划分为两类. S₃中含边u₁₁v₁₃，v₁₁u₁₂，u₁₃v₁₂的完美对集集合记为S₃¹; S₃中含边u₁₁v₁₃，v₁₁u₁₃，u₁₂v₁₂的完美对集集合记为S₃².由γ(n)的定义可知

因此，有

由(1)式和(2)，(3)式，得

由图 3知，γ(1)=6，故图 3－nK_3，3的完美对集数为γ(n)=6ⁿ

Figure (3) Reference (10)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	LOVÁSZ L, PLUMMER M. Matching Theory[M]. New York :North-Holland Press, 1986. Google Scholar
[2]	LI S L, YAN W G. The Matching Energy of Graphs with Given Parameters[J]. Discrete Applied Mathematics, 2014, 162: 415-420. doi: 10.1016/j.dam.2013.09.014 CrossRef Google Scholar
[3]	DONG F M, YAN W G, ZHANG F J. On the Number of Perfect Matchings of Line Graphs [J]. Discrete Applied Mathematics, 2013, 161(6): 794-801. doi: 10.1016/j.dam.2012.10.032 CrossRef Google Scholar
[4]	唐保祥, 任韩.图的1-因子数目的递推求法[J].浙江大学学报(理学版), 2019, 46(6):670-675. Google Scholar
[5]	唐保祥, 任韩.按匹配顶点分类的完美匹配数递推求法[J].吉林大学学报(理学版), 2019, 57(2): 286-290. Google Scholar
[6]	唐保祥, 任韩.两类特殊图 1-因子数分类递推求法[J].大连理工大学学报, 2019, 59(1):106-110. Google Scholar
[7]	唐保祥, 任韩.按饱和顶点分类的完美匹配数的递推求法[J].华南师范大学学报(自然科学版), 2019, 51(5): 110-114. Google Scholar
[8]	唐保祥, 任韩. 2类图完美匹配计数公式的嵌套递推求法[J].西南师范大学学报(自然科学版), 2019, 44(8): 23-27. Google Scholar
[9]	陈兰.完全K部图的Hosoya指标和Merrifield-Simmons指标极图[J].西南师范大学学报(自然科学版), 2019, 44(6): 14-17. Google Scholar
[10]	王文杰, 黄丽娜, 李沐春. T-型六角系统的点可区别边染色[J].西南大学学报(自然科学版), 2018, 40(10): 77-82. Google Scholar

Message Board

On Calculation Formula for Perfect Matching Number of Two Types of Graphs

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors