On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
复制标题
次三次图的导出匹配数与唯一限制匹配数的相等性
DOI：
10.1016/j.tcs.2019.11.020
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
M. Fürst;D. Rautenbach
对于图G中的匹配M，设G(M)是G的子图，G(M)的顶点与M中的一条边关联，如果G(M)是1-正则的，且M是唯一限制的，如果M是G(M)的唯一完美匹配，则G(M)是G的子图.图G的诱导匹配数νS(G)是图G中诱导匹配的最大规模，唯一限制匹配数νu r(G)是G中唯一限制匹配的最大规模。Golumbic等人(2001年)[4]提出了刻画具有νS(G)=νu r(G)的图的问题。给出了νS(G)=νu r(G)的充分大阶次2连通次三次图G的一个完全刻画.因此，我们能够证明满足νS(G)=νur(G)的次三次图G在多项式时间内是可识别的。
For a matching M in a graph G, let G (M) be the subgraph of G induced by the vertices of G that are incident with an edge in M. The matching M is induced, if G (M) is 1-regular, and M is uniquely restricted, if M is the unique perfect matching of G (M). The induced matching number ν s (G) of G is the largest size of an induced matching in G, and the uniquely restricted matching number ν u r (G) of G is the largest size of a uniquely restricted matching in G. Golumbic et al.(2001)[4] posed the problem to characterize the graphs G with ν s (G)= ν u r (G). We give a complete characterization of the 2-connected subcubic graphs G of sufficiently large order with ν s (G)= ν u r (G). As a consequence, we are able to show that the subcubic graphs G with ν s (G)= ν u r (G) can be recognized in polynomial time.
登录
查看更多内容
某些和每个最大匹配都受到唯一限制的图
影响因子：
0.9
作者：
L. Penso;D. Rautenbach;U. Souza
通讯作者：
U. Souza
影响因子：
1.1
作者：
CAMERON, K
通讯作者：
CAMERON, K
具有最大诱导匹配和最大匹配相同大小的图
DOI：
10.1016/j.disc.2004.07.022
发表时间：
2005
期刊：
Discret. Math.
影响因子：
--
作者：
K. Cameron;Tracy Walker
通讯作者：
Tracy Walker
DOI：
10.1016/j.disc.2015.06.003
发表时间：
2014
期刊：
Discret. Math.
影响因子：
--
作者：
Felix Joos;D. Rautenbach
通讯作者：
D. Rautenbach
DOI：
10.1016/j.endm.2011.05.059
发表时间：
2011
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Sounaka Mishra
通讯作者：
Sounaka Mishra