二部图匹配强迫数的谱

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

二部图匹配强迫数的谱

王洪伟

临沂师范学院理学院, 山东临沂 276005

收稿日期:2008-10-06 出版日期:2009-12-16 发布日期:2010-02-05
作者简介:王洪伟(1964), 男, 博士, 副教授，主要研究方向为组合数学与化学图论. Email: wanghw0539@sina.com
基金资助:
临沂师范学院博士科研启动基金资助项目(BS08027)

On the spectrum of matching forcing numbers for bipartite graphs

WANG Hongwei

College of Science, Linyi Normal University, Linyi 276005, Shandong, China

Received:2008-10-06 Online:2009-12-16 Published:2010-02-05

摘要/Abstract

摘要：

改进了Riddle 的尾点法, 得到自然数k属于二部图匹配强迫数谱的必要条件, 给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。

关键词: NP完全问题, 二部图, 完美匹配, 强迫数

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

中图分类号:

O1575

王洪伟. 二部图匹配强迫数的谱[J]. J4, 2009, 44(12): 30-35.

参考文献

相关文章 13

[1]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[2]	李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[3]	高超,侯新民*. 关于“给定控制数的二部图的最大边数”的一点注记[J]. J4, 2013, 48(8): 21-23.
[4]	陈宏宇1,2, 张丽3. 给定控制数的连通二部图的最大边数[J]. J4, 2012, 47(8): 11-15.
[5]	杨林1,孙磊2*. 图的某些［r,s,t］-染色的色数[J]. J4, 2012, 47(6): 80-82.
[6]	李振琳,卢君龙,吕新忠. 关于图的符号边全控制[J]. J4, 2012, 47(6): 83-86.
[7]	曹雷1,2,郭嘉丰1,程学旗1. 基于二部图半监督方法的查询日志实体挖掘[J]. J4, 2012, 47(5): 32-37.
[8]	卢建立,蔡文娟. 均衡二部图中含指定顶点独立6-圈的个数[J]. J4, 2010, 45(12): 5-11.
[9]	邹青松李硕杨兴刚. 二部图中包含六圈的度条件[J]. J4, 2009, 44(8): 13-15.
[10]	何文玉，陈祥恩*. 完全二部图K5,n的点可区别IE全染色[J]. J4, 2009, 44(2): 91-96.
[11]	耿建艳,颜谨,李峰 . 二部图中含指定顶点的独立4-圈[J]. J4, 2008, 43(5): 87-92 .
[12]	马巧灵,张苏梅 . 一类二部图的(d,1)-全标号[J]. J4, 2008, 43(2): 109-112 .
[13]	王纪辉, . 关于近似二部图边覆盖染色的一个充分条件[J]. J4, 2006, 41(1): 21-23 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed