二部图匹配强迫数的谱

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.

参考文献

相关文章 15

[1]	徐正权,邓凯. 7个苯环生成的六角系统的自由度与反自由度[J]. 《山东大学学报(理学版)》, 2026, 61(2): 115-126.
[2]	郭亚勤,陈祥恩. 完全二部图K1,n、K2,n、K3,n的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 24-33.
[3]	胡开洋,黄明芳,马宝林. 完全二部图K_{12, n}(12≤n≤88)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 36-43, 70.
[4]	尹会玲,陈京荣,苏晓艳. 星图与二部图的某些乘积图上的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2023, 58(6): 18-24, 39.
[5]	韩慧,刘雨童,姚海元. 梯子图双强迫多项式的递推求解[J]. 《山东大学学报(理学版)》, 2023, 58(11): 127-134, 146.
[6]	孙晓玲,高玉斌,杜建伟,任建斌. 准树图的零阶广义Randic指数[J]. 《山东大学学报(理学版)》, 2022, 57(12): 96-102.
[7]	索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[8]	杨瑞,刘成立,武楠楠. n棱柱的完美匹配计数及其k-共振性[J]. 《山东大学学报(理学版)》, 2022, 57(11): 37-41.
[9]	来金花,刘蒙蒙. 含有完美匹配树的最小Steiner k-Wiener指标[J]. 《山东大学学报(理学版)》, 2022, 57(10): 66-71.
[10]	王霞,边红,于海征. 整可逆图的克罗内克积的逆[J]. 《山东大学学报(理学版)》, 2021, 56(11): 87-92.
[11]	包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[12]	王倩. k-连通图中生成树和完美匹配上的可收缩边[J]. 山东大学学报（理学版）, 2016, 51(8): 29-34.
[13]	李世玲, 陈祥恩,王治文. 完全二部图K3,n(n≥18)的点可区别E-全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 68-71.
[14]	高超,侯新民*. 关于“给定控制数的二部图的最大边数”的一点注记[J]. J4, 2013, 48(8): 21-23.
[15]	陈宏宇1,2, 张丽3. 给定控制数的连通二部图的最大边数[J]. J4, 2012, 47(8): 11-15.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed