Counting independent sets in Riordan graphs

DOI10.1016/J.DISC.2020.112043zbMATH Open1447.05106arXiv2006.16579OpenAlexW3038218193MaRDI QIDQ2198385FDOQ2198385

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

Publication date: 10 September 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2006.16579

Recommendations

• Counting independent sets in graphs
• Counting Independent Sets in Hypergraphs
• Counting independent sets in tricyclic graphs
• Counting independent sets in triangle-free graphs
• Counting independent sets in some classes of (almost) regular graphs
• The number of independent sets in graphs
• Counting independent sets in regular hypergraphs
• Counting independent sets in graphs of hyperplane arrangements
• Counting independent sets in cocomparability graphs
• Counting the number of independent sets in chordal graphs

zbMATH Keywords

Hamiltonian pathindependent setFibonacci numberToeplitz graphPell numberRiordan graphpattern avoiding sequence

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Enumeration in graph theory (05C30) Combinatorics on words (68R15) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cites Work

• Hamiltonian properties of Toeplitz graphs
• Characterizing bipartite Toeplitz graphs
• Title not available (Why is that?)
• String overlaps, pattern matching, and nontransitive games
• On the chromatic number of integral circulant graphs
• Counting independent sets in graphs
• On the chromatic number of Toeplitz graphs
• Independent sets on path-schemes
• Toeplitz graph decomposition
• Riordan graphs I: structural properties
• Riordan graphs. II: Spectral properties
• Structural properties of Toeplitz graphs
• Title not available (Why is that?)

Cited In (10)

• Encoding labelled \(p\)-Riordan graphs by words and pattern-avoiding permutations
• Counting independent sets in some classes of (almost) regular graphs
• Enumeration of bipartite non-crossing geometric graphs
• Counting independent sets in regular hypergraphs
• Diameter of io-decomposable Riordan graphs of the Bell type
• Counting independent sets in tricyclic graphs
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Riordan graphs I: structural properties
• Riordan graphs. II: Spectral properties
• Title not available (Why is that?)

This page was built for publication: Counting independent sets in Riordan graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198385)