NP-completeness of anti-Kekul\'e and matching preclusion problems

Huazhong Lü, Xianyue Li, Heping Zhang

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

Knowledge Graph



Sign up or login to leave a comment