\(K\)-Coverable Polyhex Graphs

A polyhex graph is either a hexagonal system or a coronoid system. A polyhex graph \(G\) is said to be \(k\)-coverable if for any \(k\) mutually disjoint hexagons the subgraph obtained from \(G\) by deleting all these \(k\) hexagons together with their incident edges has at least one perfect matching. In this paper, a constructive criterion is given to determine whether or not a given polyhex graph is \(k\)-coverable. Furthermore, a simple method is developed which allows us to determine whether or not there exists a \(k\)-coverable polyhex graph with exactly \(h\) hexagons.