n棱柱的完美匹配计数及其k-共振性

doi:10.6040/j.issn.1671-9352.0.2020.518

《山东大学学报(理学版)》 ›› 2022, Vol. 57 ›› Issue (11): 37-41.doi: 10.6040/j.issn.1671-9352.0.2020.518

• • 上一篇

n棱柱的完美匹配计数及其k-共振性

杨瑞,刘成立,武楠楠

河南理工大学数学与信息科学学院, 河南焦作 454003

发布日期:2022-11-10
作者简介:杨瑞(1983— ),女,博士,讲师,研究方向为图论及其应用.E-mail:yangrui@hpu.edu.cn
基金资助:
国家自然科学基金资助项目(11801148,11626089);河南理工大学博士基金项目(B2014-060)

The number of perfect matchings and k-resonance in n-prism

YANG Rui, LIU Cheng-li, WU Nan-nan

School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo 454003, Henan, China

Published:2022-11-10

摘要/Abstract

摘要： 当n≥3时,笛卡尔积图C_n×P₂是一个多面体图,也称为n棱柱,其中C_n为n长圈,P₂为2长路。令G是一个n棱柱的平面嵌入图,k是正整数,若对任意的正整数i(0≤i≤k),从图G中任意删除掉i个两两不交的偶面所得到的图有完美匹配,则称图G是k-共振的。首先得到n棱柱完美匹配数的计算公式;然后对n棱柱的共振性进行讨论,得到了n棱柱是1-共振、2-共振的和k-共振的(k≥3)。

关键词: 完美匹配, 笛卡尔积图, n棱柱, k-共振

Abstract: For n≥3, the cartesian product C_n×P2 is a polyhedral graph, the n-prism, where C_n is a n-cycle and P2 is a 2-path. Let G be a plane embedded graph of n-prism and k be a positive integer, the graph G is k-resonant, if the graph obtained by deleting any i pairwise disjoint even faces from the graph G has a perfect matching for any positive integer i(0≤i≤k). The formula of the number of perfect matchings in n-prism is obtained. Then the resonance of n-prism is discussed, its 1-resonance, 2-resonance and k-resonance are obtained(k≥3).

Key words: perfect matching, cartesian product graph, n-prism, k-resonant

中图分类号:

O157.6

杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.

YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.

参考文献

[1] LOVÁSZ L, PLUMMER M D. Matching theory[M]. New York: North-Holland Press, 1986.
[2] PAULING L. The nature of chemical bond[M]. New York: Ithaca University Press, 1939.
[3] VALIANTL G. The complexity of computing the permanent[J]. Theoretical Compute Science, 1979, 8(2):189-201.
[4] 唐保祥, 李刚, 任韩. 3类图完美匹配的数目[J]. 浙江大学学报(理学版), 2011, 38(4):16-19. TANG Baoxiang, LI Gang, REN Han. The number of the prefect matchings in three types of graphs[J]. Journal of Zhejiang University(Natural Science), 2011, 38(4):16-19.
[5] 唐保祥, 任韩. 4类图完美匹配的计数[J]. 武汉大学学报(理学版), 2012, 58(5):441-446. TANG Baoxiang, REN Han. The number of the prefect matchings for four types of graphs[J]. Journal of Wuhan University(Natural Science), 2012, 58(5):441-446.
[6] YANG Rui, ZHANG Heping. 2-Resonant fullerenes[J]. European Journal of Combinatorics, 2015, 49:13-24.
[7] ZHANG Heping, LIU Saihua. 2-Resonance of plane bipartite graphs and its applications to boron-nitrogen fullerenes[J]. Discrete Applied Mathematics, 2010, 158(14):1559-1569.
[8] SHIU W C, ZHANG Heping. A complete characterization for k-resonant Klein-bottle polyhexes[J]. Journal of Mathematical Chemistry, 2008, 43(1):45-59.
[9] ZHANG Fuji, WANG Lusheng. k-Resonance of open-ended carbon nanotubes[J]. Journal of Mathematical Chemistry, 2004, 35(2):87-103.
[10] BONDY J A, MURTY U S R. Graph theory[M]. New York: Springer, 2008.
[11] BRUALDI R A. Introductory combinatorics[M]. New York: North-Holland Press, 2009.
[12] DIESTEL R. Graph theory[M]. 5th ed. Berlin: Springer, 2017.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

n棱柱的完美匹配计数及其k-共振性

The number of perfect matchings and k-resonance in n-prism

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

多维度评价

本文评价

推荐阅读 0

[1]	来金花,刘蒙蒙. 含有完美匹配树的最小Steiner k-Wiener指标[J]. 《山东大学学报(理学版)》, 2022, 57(10): 66-71.
[2]	王霞,边红,于海征. 整可逆图的克罗内克积的逆[J]. 《山东大学学报(理学版)》, 2021, 56(11): 87-92.
[3]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[4]	王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.