J4 ›› 2009, Vol. 44 ›› Issue (12): 30-35.

• Articles • Previous Articles     Next Articles

On the spectrum of matching forcing numbers for bipartite graphs

WANG Hongwei   

  1. College of Science, Linyi Normal University, Linyi 276005, Shandong, China
  • Received:2008-10-06 Online:2009-12-16 Published:2010-02-05

PDF (PC)

1157

Abstract:

The trailingvertex method in essence is improved, a necessary condition for the forcing number of  perfect matching equals to a given natural number k for a bipartite graph is obtained, and a necessary and sufficient condition for the minimum forcing number equals  the minimum number of trailing vertices of all standard orderings of a color set is given.

Key words: bipartite graph, perfect matching, forcing number, NPcomplete

CLC Number: 

  • O1575
[1] XU Zhengquan, DENG Kai. Degree of freedom and anti-degree of freedom of a hexagonal system generated by seven benzene rings [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(2): 115-126.
[2] GUO Yaqin, CHEN Xiangen. E-total colorings of complete bipartite graphs K1,n, K2,n and K3,n which are vertex-distinguished by multiple sets [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(2): 24-33.
[3] Kaiyang HU,Mingfang HUANG,Baolin MA. Vertex-distinguishing E-total coloring of complete bipartite graph K12, n for 12≤n≤88 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(6): 36-43, 70.
[4] Huiling YIN,Jingrong CHEN,Xiaoyan SU. The k-path vertex cover in some products graphs of star graph and bipartite graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 18-24, 39.
[5] Hui HAN,Yutong LIU,Haiyuan YAO. Recursive solving of di-forcing polynomials for ladder graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 127-134, 146.
[6] SUN Xiao-ling, GAO Yu-bin, DU Jian-wei, REN Jian-bin. Zeroth-order general Randic index of quasi-tree graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 96-102.
[7] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[8] 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.
[9] 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.
[10] 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.
[11] . Vertex-distinguishing E-total coloring of complete bipartite graph K10,n with 10≤n≤90 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 23-30.
[12] 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.
[13] LI Shi-ling, CHEN Xiang-en, WANG Zhi-wen. Vertex-Distinguishing E-Total coloring of complete bipartite graph K3,n with n≥18 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 68-71.
[14] GAO Chao, HOU Xin-min*. Some remarks on maximum size of bipartite graphs with a given domination number [J]. J4, 2013, 48(8): 21-23.
[15] CHEN Hong-yu1,2, ZHANG Li3. Maximum number of edges in connected bipartite graphs with  a given domination number [J]. J4, 2012, 47(8): 11-15.
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