A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs. Issue 1 (12th March 2015)

• Record Type: Journal Article
• Authors: Alexander, James; Mink, Tim
• Is Part Of: Journal of graph theory. Volume 81:Issue 1(2016)
• Page Start: 57
• Page End: 72
• Publication Date: 2015-03-12
• Subjects: independent sets -- minimum degree -- cliques -- subgraph enumeration -- extremal graph theory -- regular graphs -- Moore graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21861
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.