Enumerating independent vertex sets in grid graphs

Seungsang Oh, Sangyop Lee

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


A set of vertices in a graph is called independent if no two vertices of the set are connected by an edge. In this paper we use the state matrix recursion algorithm, developed by Oh, to enumerate independent vertex sets in a grid graph and even further to provide the generating function with respect to the number of vertices. We also enumerate bipartite independent vertex sets in a grid graph. The asymptotic behavior of their growth rates is presented.

Original languageEnglish
Pages (from-to)192-204
Number of pages13
JournalLinear Algebra and Its Applications
Publication statusPublished - 2016 Dec 1


  • Enumeration
  • Hard square
  • Independent vertex set
  • Merrifield–Simmons index

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Enumerating independent vertex sets in grid graphs'. Together they form a unique fingerprint.

Cite this