NP-completeness of anti-Kekulé and matching preclusion problems

Huazhong Lü, Xianyue Li, Heping Zhang

Published 2017-06-28Version 1

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$.