標題: CONDITIONAL MATCHING PRECLUSION FOR THE STAR GRAPHS
作者: Cheng, Eddie
Liptak, Laszlo
Hsu, Lih-Hsing
Tan, Jimmy J. M.
Lin, Cheng-Kuan
資訊工程學系
Department of Computer Science
關鍵字: Interconnection networks;perfect matching;star graphs
公開日期: 1-Apr-2015
摘要: The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number and classify all optimal sets for the star graphs, one of the most popular interconnection networks.
URI: http://hdl.handle.net/11536/124685
ISSN: 0381-7032
期刊: ARS COMBINATORIA
Volume: 120
起始頁: 369
結束頁: 382
Appears in Collections:Articles