Independent sets in graphs

DOI10.1515/DMA-2016-0028zbMath1352.05144OpenAlexW2565379865MaRDI QIDQ501998

Aleksandr B. Dainyak, Alexander A. Sapozhenko

Publication date: 10 January 2017

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2016-0028

zbMATH Keywords

enumerationdominationindependent setsextremal graph theory

Mathematics Subject Classification ID

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

Related Items (6)

Turán-type results for distance graphs in an infinitesimal plane layer ⋮ On the number of independent sets in simple hypergraphs ⋮ Trees with extremal numbers of \(k\)-dominating sets ⋮ On the number of independent and \(k\)-dominating sets in graphs with average vertex degree at most \(k\) ⋮ Trees without twin-leaves with smallest number of maximal independent sets ⋮ Independence polynomials of bipartite graphs

Uses Software

• OCOTILLO

Cites Work

• Maximal independent sets in the covering graph of the cube
• A note on eigenvalue bounds for independence numbers of non-regular graphs
• Independent sets in graphs with given minimum degree
• On a division property of consecutive integers
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Extremal problems for independent set enumeration
• Two problems on independent sets in graphs
• The number of independent sets in a graph with small maximum degree
• Enumerating maximal independent sets with applications to graph colouring.
• Augmenting graphs for independent sets
• Estimates of the number of independent sets in graphs with a fixed independence number
• Independent sets in quasi-regular graphs
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• The maximum number of maximal independent sets in unicyclic connected graphs
• Eigenvalue bounds for independent sets
• Trees with extremal numbers of maximal independent sets including the set of leaves
• Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number
• On the number of independent sets in a tree
• On the maximum number of cliques in a graph
• Graphs with the second largest number of maximal independent sets
• A generalization of the Motzkin-Straus theorem to hypergraphs
• Molecular graphs and the inverse Wiener index problem
• A sharp upper bound for the number of stable sets in graphs with given number of cut edges
• The second largest number of maximal independent sets in graphs with at most \(k\) cycles
• Matchings and independent sets of a fixed size in regular graphs
• Trees with the second largest number of maximal independent sets
• More spectral bounds on the clique and independence numbers
• The maximum number of cliques in dense graphs
• Graphs with unique maximum independent sets
• Another extremal problem for Turan graphs
• The number of maximal independent sets in a connected graph
• A note on Ramsey numbers
• Independent sets in regular graphs and sum-free subsets of finite groups
• A generalization of Hölder's inequality and some probability inequalities
• Relations between packing and covering numbers of a tree
• The maximum number of q-cliques in a graph with no p-clique
• The number of maximal independent sets in connected triangle-free graphs
• The Shannon capacity of a union
• On independent domination number of regular graphs
• A note on the approximation of a minimum-weight maximal independent set
• Maximal independent sets in graphs with at most one cycle
• Generalized independence and domination in graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Bipartite graphs can have any number of independent sets
• A new Turán-type theorem for cliques in graphs
• Lower bounds on the independence number in terms of the degrees
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• The second largest number of maximal independent sets in connected graphs with at most one cycle
• Independent domination in graphs: A survey and recent results
• New approach to the \(k\)-independence number of a graph
• On computing boundary functional sums
• Counting sum-free sets in abelian groups
• Comments on: Donald E. Knuth, ``The sandwich theorem
• New lower bounds for the Shannon capacity of odd cycles
• Bounds on the number of vertex independent sets in a graph
• Upper bound for the number of independent sets in graphs
• Almost all trees have an even number of independent sets
• Large independent sets in regular graphs of large girth
• Independent sets in regular graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• Independent sets in triangle-free cubic planar graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• A generalization of a theorem of Turán
• A finiteness theorem for maximal independent sets
• The number of independent sets in unicyclic graphs
• On \(k\)-independence in graphs with emphasis on trees
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Counting independent sets up to the tree threshold
• Introduction to Random Graphs
• Maximal independent sets in bipartite graphs
• On replica symmetry of large deviations in random graphs
• Maximal and maximum independent sets in graphs with at mostr cycles
• The Shannon capacity of a graph and the independence numbers of its powers
• The Number of Independent Sets in a Regular Graph
• Measure and conquer
• The Number of Maximal Independent Sets in a Tree
• Smallest-last ordering and clustering and graph coloring algorithms
• A fast parallel algorithm for the maximal independent set problem
• A Note on Independent Sets in Trees
• The number of maximal independent sets in connected graphs
• On maximal independent sets of nodes in trees
• On graphs with polynomially solvable maximum-weight clique problem
• Some Ramsey-Type Numbers and the Independence Ratio
• The Independence Ratio of Regular Graphs
• Component behavior near the critical point of the random graph process
• The structure and maximum number of maximum independent sets in trees
• Cliques in random graphs
• On the Shannon capacity of a graph
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Constraints on the number of maximal independent sets in graphs
• The Number of Independent Sets in a Grid Graph
• A limit theorem for the Shannon capacities of odd cycles I
• Independent sets in asteroidal triple-free graphs
• A nontrivial lower bound on the shannon capacities of the complements of odd cycles
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• Paths in graphs
• On the number of independent sets in expanders
• A limit theorem for the Shannon capacities of odd cycles. II
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On the independence number of sparse graphs
• The Merrifield–Simmons Conjecture Holds for Bipartite Graphs
• On Dominating Sets and Independent Sets of Graphs
• Maximal independent sets in radio networks
• Information Inequalities for Joint Distributions, With Interpretations and Applications
• An upper bound on the number of cliques in a graph
• On the Independent Domination Number of Random Regular Graphs
• Finding Large Independent Sets in Graphs and Hypergraphs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Independent sets, matchings, and occupancy fractions
• Maximizing the Number of Independent Sets of a Fixed Size
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• On the number of independent sets in graphs with fixed independence number
• An upper bound for the number of maximal independent sets in a graph
• Stochastic Algorithms: Foundations and Applications
• Turán Graphs, Stability Number, and Fibonacci Index
• An inequality for the chromatic number of a graph
• On the number of complete subgraphs and circuits contained in graphs
• On the number of independent sets in damaged Cayley graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• On cliques in graphs
• The number of maximum independent sets in graphs
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
• A new proof of the independence ratio of triangle-free cubic graphs
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Independent sets in graphs