Matching preclusion number in product graphs
Matching preclusion number in product graphs
复制标题
产品图中的匹配排除数
DOI：
10.1016/j.tcs.2018.06.050
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
毛亚平
中科院分区：
文献类型：
--
作者：
王兆;Christopher Melekian;Eddie Cheng;毛亚平
图的排除数是图的边的最小数目，这些边的删除会导致图没有完美匹配或几乎完美匹配。对于许多互连网络，匹配排除数等于网络中一个顶点的最小次数，而达到最小次数的边集正是那些关联到单个最小度顶点的边集，我们称这种网络为超匹配网络。本文给出了用各种二叉图运算构造的网络的匹配排除数的上下界，并给出了这类网络是超匹配的充分条件。
Thematching preclusion numberof a graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings or almost-perfect matchings. For many interconnection networks, the matching preclusion number is equal to the minimum degree of a vertex in the network, and the sets of edges attaining the minimum are precisely those incident to a single vertex of minimum degree; we say such networks aresuper matched. In this paper we derive upper and lower bounds for the matching preclusion number for networks constructed using a variety of binary graph operations, and give sufficient conditions for such networks to be super matched.
登录
查看更多内容
影响因子：
1
作者：
S. Hsieh;Pei-Yu Yu-Pei-Yu-Yu-2114104759
通讯作者：
S. Hsieh;Pei-Yu Yu-Pei-Yu-Yu-2114104759
DOI：
10.1201/b10959
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
R. Hammack;W. Imrich;S. Klavžar
通讯作者：
R. Hammack;W. Imrich;S. Klavžar
DOI：
10.1016/j.jcss.2013.01.013
发表时间：
2013-08
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Nai-Wen Chang;S. Hsieh
通讯作者：
Nai-Wen Chang;S. Hsieh
影响因子：
2.1
作者：
M. C. Dourado;D. Meierling;L. Penso;D. Rautenbach;Fábio Protti;Aline Ribeiro de Almeida
通讯作者：
M. C. Dourado;D. Meierling;L. Penso;D. Rautenbach;Fábio Protti;Aline Ribeiro de Almeida
影响因子：
2.1
作者：
F. Ordóñez;Jiamin Zhao
通讯作者：
F. Ordóñez;Jiamin Zhao