Counting dominating sets and related structures in graphs

DOI10.1016/J.DISC.2015.12.011zbMath1333.05145arXiv1503.00998OpenAlexW2963065479MaRDI QIDQ271644

Jonathan Cutler, Andrew John Radcliffe

Publication date: 7 April 2016

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

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

zbMATH Keywords

dominating setsextremal enumerationShearer's lemma

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 (1)

Maximizing and minimizing the number of generalized colorings of trees

Cites Work

• Bounds on the maximum number of minimum dominating sets
• Maximizing proper colorings on graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Errata to: The number of fixed points of the majority rule
• Legal coloring of graphs
• Some intersection theorems for ordered sets and graphs
• The number of fixed points of the majority rule
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Maximizing the number of q -colorings
• The Number of Independent Sets in a Regular Graph
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• On weighted graph homomorphisms
• Algorithms and Computation
• On cliques in graphs

This page was built for publication: Counting dominating sets and related structures in graphs