{
  "id": "1706.09321",
  "version": "v1",
  "published": "2017-06-28T14:35:16.000Z",
  "updated": "2017-06-28T14:35:16.000Z",
  "title": "NP-completeness of anti-Kekulé and matching preclusion problems",
  "authors": [
    "Huazhong Lü",
    "Xianyue Li",
    "Heping Zhang"
  ],
  "comment": "9 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Anti-Kekul\\'{e} problem is a concept of chemical graph theory precluding the Kekul\\'{e} structure of molecules. Matching preclusion and conditional matching preclusion were proposed as measures of robustness in the event of edge failure in interconnection networks. It is known that matching preclusion problem on bipartite graphs is NP-complete. In this paper, we mainly prove that anti-Kekul\\'{e} problem on bipartite graphs is NP-complete. As an extension to (conditional) matching preclusion problem, we propose the concept of $s$-restricted matching preclusion problem, and prove that such problem on bipartite graphs is also NP-complete. Finally, we determine that $s$-restricted matching preclusion number of $Q_n$ ($n\\geq3$) is $2n-2$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-28T14:35:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graphs",
      "np-completeness",
      "interconnection networks",
      "conditional matching preclusion",
      "chemical graph theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}