Independent Sets of m,n-gonal Graphs

Asekha Khantavchai, Thiradet Jiarasuksakun

Abstract

An m,n-gonal system pi=(V,E,F), where V is a vertex set, E is an edge set and F is a face set, is a graph of cyclic hydrocarbon molecules: each vertex represents a carbon atom and each edge represents a chemical bond. A Kekule structure, K\subseteq E  is a perfect matching and the edges of  the matching correspondto double bonds. We count a number of perfect matchings (Kekule structures) in m,n-gonal systems where  m,n = 2(mod4). Ourresult is shown that the number of perfect matchings is phi(pi)=|detA(pi)|, where A(pi) is a biadjacency matrix for each system.

Moreover, we study the interesting properties of  vertex and face independence sets of m,n-gonal systems.