Counting independent sets in Riordan graphs

DOI10.1016/J.DISC.2020.112043MaRDI QIDQ2198385zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6007883 (Why is no real title available?)
• scientific article; zbMATH DE number 3839993 (Why is no real title available?)
• Characterizing bipartite Toeplitz graphs
• Counting independent sets in graphs
• Hamiltonian properties of Toeplitz graphs
• Independent sets on path-schemes
• On the chromatic number of Toeplitz graphs
• On the chromatic number of integral circulant graphs
• Riordan graphs I: structural properties
• Riordan graphs. II: Spectral properties
• String overlaps, pattern matching, and nontransitive games
• Structural properties of Toeplitz graphs
• Toeplitz graph decomposition

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
• Riordan graphs I: structural properties
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Riordan graphs. II: Spectral properties
• scientific article; zbMATH DE number 3891427 (Why is no real title available?)

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)