Counting independent sets in Riordan graphs

Gi-Sang Cheon, Ji-Hwan Jung, Bumtle Kang, Hana Kim, Suh-Ryung Kim, Sergey Kitaev, Seyed Ahmad Mojallal

Research output: Contribution to journalArticle

Abstract

The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs.

In this paper, we give exact enumeration and lower and upper bounds
for the number of independent sets for various classes of Riordan
graphs. Remarkably, we offer a variety of methods to solve the
problems that range from the structural decomposition theorem to
methods in combinatorics on words. Some of our results are valid for
any graph.
Original languageEnglish
Article number112043
Number of pages20
JournalDiscrete Mathematics
Volume343
Issue number11
Early online date3 Jul 2020
Publication statusE-pub ahead of print - 3 Jul 2020

Keywords

  • Riordan graph
  • Toeplitz graph
  • independent set
  • pattern avoiding sequence
  • Fibonacci number
  • Pell number
  • Hamiltonian path

Fingerprint Dive into the research topics of 'Counting independent sets in Riordan graphs'. Together they form a unique fingerprint.

  • Cite this

    Cheon, G-S., Jung, J-H., Kang, B., Kim, H., Kim, S-R., Kitaev, S., & Mojallal, S. A. (2020). Counting independent sets in Riordan graphs. Discrete Mathematics, 343(11), [112043].