CONDITIONAL MATCHING PRECLUSION FOR THE STAR GRAPHS

Eddie Cheng, Liptak Laszlo, Lih Hsing Hsu, Jiann-Mean Tan, Cheng-Kuan Lin

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.
Original languageEnglish
Pages (from-to)369-382
Number of pages14
JournalArs Combinatoria
StatePublished - Apr 2015

Keywords

  • Interconnection networks; perfect matching; star graphs
  • HAMILTONIAN-LACEABILITY

Fingerprint Dive into the research topics of 'CONDITIONAL MATCHING PRECLUSION FOR THE STAR GRAPHS'. Together they form a unique fingerprint.

Cite this