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)

913

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] 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.
[2] 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.
[3] 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.
[4] 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.
[5] YANG Lin1, SUN Lei2*. Some ［r,s,t］-chromatic number of graphs [J]. J4, 2012, 47(6): 80-82.
[6] LI Zhen-lin, LU Jun-long, L Xin-zhong. On signed edge total domination of graphs [J]. J4, 2012, 47(6): 83-86.
[7] CAO Lei1,2, GUO Jia-feng1, CHENG Xue-qi1. Bipartite graph based semi-supervised method for entity mining from the query log [J]. J4, 2012, 47(5): 32-37.
[8] DING Lu-shun, YAN Jin. he Z3-connectivity for 3-regular graph [J]. J4, 2012, 47(12): 22-24.
[9] LI Ze-peng1, WANG Zhi-wen2, CHEN Xiang-en1*. Adjacent-vertex-distinguishing total coloring of planar bipartite graphs [J]. J4, 2011, 46(4): 4-8.
[10] LU Jian-li, CAI Wen-juan. The number of vertex-disjoint 6-cycles containing specified vertices in a balance bipartite graph [J]. J4, 2010, 45(12): 5-11.
[11] JU Jing-Song, LI Shuo, YANG Xin-Gang. Degree conditions for bipartite graphs to contain 6-cycles [J]. J4, 2009, 44(8): 13-15.
[12] . Vertex distinguishing IEtotal chromatic numbers of  complete bipartite graph K5,n [J]. J4, 2009, 44(2): 91-96.
[13] LI Feng,GENG Jian-yan,LI Shuo,LIANG Feng . A partition of bipartite graphs with 4-cycle and 8-cycle [J]. J4, 2008, 43(6): 15-18 .
[14] GENG Jian-yan,YAN Jin,LI Feng . Vertex-disjoint 4-cycle in a bipartite graph [J]. J4, 2008, 43(5): 87-92 .
[15] MA Qiao-ling,ZHANG Su-mei . The total labelling number of some bipartite graphs [J]. J4, 2008, 43(2): 109-112 .
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