Enumerating independent vertex sets in grid graphs

Seungsang Oh; Sangyop Lee

doi:10.1016/j.laa.2016.08.025

Enumerating independent vertex sets in grid graphs

Seungsang Oh, Sangyop Lee

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	192-204
Number of pages	13
Journal	Linear Algebra and Its Applications
Volume	510
DOIs	https://doi.org/10.1016/j.laa.2016.08.025
Publication status	Published - 2016 Dec 1

Keywords

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

Access to Document

10.1016/j.laa.2016.08.025

Cite this

@article{7bc4f29ab55a437d8e021d444b528f86,

title = "Enumerating independent vertex sets in grid graphs",

abstract = "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.",

keywords = "Enumeration, Hard square, Independent vertex set, Merrifield–Simmons index",

author = "Seungsang Oh and Sangyop Lee",

year = "2016",

month = dec,

day = "1",

doi = "10.1016/j.laa.2016.08.025",

language = "English",

volume = "510",

pages = "192--204",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Enumerating independent vertex sets in grid graphs

AU - Oh, Seungsang

AU - Lee, Sangyop

PY - 2016/12/1

Y1 - 2016/12/1

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

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

KW - Enumeration

KW - Hard square

KW - Independent vertex set

KW - Merrifield–Simmons index

UR - http://www.scopus.com/inward/record.url?scp=84983567710&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983567710&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2016.08.025

DO - 10.1016/j.laa.2016.08.025

M3 - Article

AN - SCOPUS:84983567710

SN - 0024-3795

VL - 510

SP - 192

EP - 204

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Enumerating independent vertex sets in grid graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this