On the anti-Kekule number of k-polyomino system

Abstract

The anti-Kekulé number of a graph G with a perfect matching, is defined to be the minimum number of edges that should be deleted such that the remaining graph is connected and contains no perfect matchings. This graph parameter finds potential applications in chemistry, especially in the stability and resonance energy of chemical compounds. For a graph G and a fixed positive integer γ, the problem of finding whether the anti-Kekulé number of G is less than γ, is NP-complete. The anti-Kekulé number of parallelograms, catacondensed benzenoids, fullerenes, triangular, rectangular and hexagonal grids has been investigated in a number of papers. In this paper, we propose the concepts of permitted induced subgraph and matching-based edge partitions in chemical graphs which help us to compute lower and upper bounds respectively on the anti-Kekuté number. We further use these concepts to investigate the anti-Kekulé number of k-polyomino system which is a finite 2-connected plane graph such that each interior face (also called cell) is surrounded by a regular 4k-cycle of length one. First, we calculate the exact value of the anti-Kekué number of k-polyomino system for k = 1,2. Finally, we prove the result for general k-polyomino system by induction on k.

Publication
Utilitas Mathematica