JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (11): 37-41.doi: 10.6040/j.issn.1671-9352.0.2020.518

Previous Articles    

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

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

  1. School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo 454003, Henan, China
  • Published:2022-11-10

PDF (PC)

105

Abstract: For n≥3, the cartesian product Cn×P2 is a polyhedral graph, the n-prism, where Cn 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

CLC Number: 

  • O157.6
[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.
[1] LAI Jin-hua, LIU Meng-meng. On minimum Steiner k-Wiener index of trees with perfect matching [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 66-71.
[2] WANG Xia, BIAN Hong, YU Hai-zheng. Inverse of Kronecker product of integrally invertible graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 87-92.
[3] WANG Qian. The contractible edges of a spanning tree and a perfect matching in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 29-34.
[4] LIU Xin-sheng, DENG Wei-dong, WANG Zhi-qiang. Several conclusions of adjacent vertex distinguishing E-total coloring of the cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 5-8.
[5] . On the spectrum of matching forcing numbers for bipartite graphs [J]. J4, 2009, 44(12): 30-35.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd