A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs

DOI10.1002/jgt.21861zbMath1330.05115arXiv1308.3242MaRDI QIDQ3466354

Tim Mink, James Alexander

Publication date: 1 February 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

regular graphsminimum degreecliquesindependent setsextremal graph theorysubgraph enumerationMoore graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C30: Enumeration in graph theory

05C12: Distance in graphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C07: Vertex degrees

Related Items

Maximizing the Number of Independent Sets of a Fixed Size, On the critical group of the missing Moore graph, Many cliques with few edges and bounded maximum degree, Homomorphisms into loop-threshold graphs, The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

Cites Work

• Unnamed Item
• Independent sets in graphs with given minimum degree
• Extremal problems for independent set enumeration
• Two problems on independent sets in graphs
• The Hilbert series of the face ring of a flag complex
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Entropy, independent sets and antichains: A new approach to Dedekind’s problem
• On Sets of Acquaintances and Strangers at any Party
• The Number of Independent Sets in a Regular Graph
• A logical expansion in mathematics
• Maximizing H‐Colorings of a Regular Graph
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree