Independent sets in certain classes of (almost) regular graphs

2003/10/23 by Alexander Burstein, Burstein, Alexander, Sergey Kitaev +3
Computer Science · Mathematics · #05A05 #05A15 (Primary) 30B70 #42C05 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #math.CO #msc:05A05 #msc:05A15 #msc:30B70 #msc:42C05

paper · pdf · doi:10.48550/arxiv.math/0310379

11 pages, 5 figures

arxiv created 2003/10/23 · openalex publication_date 2003/10/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We enumerate the independent sets of several classes of regular and almost regular graphs and compute the corresponding generating functions. We also note the relations between these graphs and other combinatorial objects and, in some cases, construct the corresponding bijections.

Related

• Counting independent sets in graphs
• Minimizing the number of independent sets in triangle-free regular graphs
• Counting independent sets in expanding bipartite regular graphs
• A new method for enumerating independent sets of a fixed size in general graphs
• Number of Independent Sets in Regular and Irregular Graphs: A 31 Year Journey