Counting dominating sets and related structures in graphs

DOI10.1016/J.DISC.2015.12.011MaRDI QIDQ271644zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: We consider some problems concerning the maximum number of (strong) dominating sets in a regular graph, and their weighted analogues. Our primary tool is Shearer's entropy lemma. These techniques extend to a reasonably broad class of graph parameters enumerating vertex colorings satisfying conditions on the multiset of colors appearing in (closed) neighborhoods. We also generalize further to enumeration problems for what we call existence homomorphisms. Here our results are substantially less complete, though we do solve some natural problems.

Recommendations

• On the total domatic number of regular graphs
• Counting minimal dominating sets
• A note on the number of dominating sets of a graph
• On maximum number of minimal dominating sets in graphs
• On the number of dominating sets in some classes of trees

Cites work

• Algorithms and Computation
• An entropy approach to the hard-core model on bipartite graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Bounds on the maximum number of minimum dominating sets
• Errata to: The number of fixed points of the majority rule
• Legal coloring of graphs
• Maximizing proper colorings on graphs
• Maximizing the number of q -colorings
• On cliques in graphs
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• On weighted graph homomorphisms
• Some intersection theorems for ordered sets and graphs
• The number of fixed points of the majority rule
• The number of independent sets in a regular graph

Cited in

(4)

• Counting representable sets on simple graphs
• Maximizing and minimizing the number of generalized colorings of trees
• Dominating Set Counting in Graph Classes
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs

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

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