Extremal problems for independent set enumeration

MaRDI QIDQ640424zbMATH OpenFDO

Authors Jonathan Cutler, Andrew John Radcliffe

Publication date 18 October 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/223259, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p169.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

lex graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Summary: The study of the number of independent sets in a graph has a rich history. Recently, Kahn proved that disjoint unions of \(K_{r,r}\)'s have the maximum number of independent sets amongst \(r\)-regular bipartite graphs. Zhao extended this to all \(r\)-regular graphs. If we instead restrict the class of graphs to those on a fixed number of vertices and edges, then the Kruskal-Katona theorem implies that the graph with the maximum number of independent sets is the lex graph, where edges form an initial segment of the lexicographic ordering. In this paper, we study three related questions. Firstly, we prove that the lex graph has the maximum number of weighted independent sets for any appropriate weighting. Secondly, we solve the problem of maximizing the number of independents sets in graphs with specified independence number or clique number. Finally, for \(m \leq n\), we find the graphs with the minimum number of independent sets for graphs with \(n\) vertices and \(m\) edges.

Recommendations

• The number of independent sets in a regular graph
• Independent sets in graphs with given minimum degree
• Extremal regular graphs: independent sets and graph homomorphisms
• On weighted graph homomorphisms
• The number of independent sets in an irregular graph

Cited in

(23)

• Extremal colorings and independent sets
• Extremal threshold graphs for matchings and independent sets
• An extension of the Win theorem: counting the number of maximum independent sets
• Counting cliques in 1-planar graphs
• Maximizing \(2\)-independents sets in \(3\)-uniform hypergraphs
• Homomorphisms into loop-threshold graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• Maximum number of fixed points in AND-OR-NOT networks
• A problem of Laczkovich: how dense are set systems with no large independent sets?
• Cliques in graphs excluding a complete graph minor
• A new method for enumerating independent sets of a fixed size in general graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Independent sets in graphs
• Tree densities in sparse graph classes
• Expanding operators for the independent set problem
• Extremal graphs for homomorphisms. II
• Counting independent sets of a fixed size in graphs with a given minimum degree
• On a conjecture of Nagy on extremal densities
• Minimal enumerations of subsets of a finite set and the middle level problem
• Solution to a problem of Katona on counting cliques of weighted graphs
• On the activities and partitions of the vertex subsets of graphs
• On the number of independent sets in Halin graphs
• Counting and enumerating independent sets with applications to combinatorial optimization problems

This page was built for publication: Extremal problems for independent set enumeration

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