Toward a Nordhaus-Gaddum inequality for the number of dominating sets

DOI10.2140/INVOLVE.2019.12.1175zbMATH Open1428.05234arXiv1808.05576OpenAlexW2885810669WikidataQ126985877 ScholiaQ126985877MaRDI QIDQ2278638FDOQ2278638

Authors: Lauren Keough, David Shane 

Publication date: 5 December 2019

Published in: Involve (Search for Journal in Brave)

Abstract: A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex of $G$ is either in $S$ or is adjacent to a vertex in $S$. Nordhaus-Gaddum inequailties relate a graph $G$ to its complement $$. In this spirit Wagner proved that any graph $G$ on $n$ vertices satisfies $$ where $partial(G)$ is the number of dominating sets in a graph $G$. In the same paper he comments that an upper bound for $$ among all graphs on $n$ vertices seems to be much more difficult. Here we prove an upper bound on $$ and prove that any graph maximizing this sum has minimum degree at least $lfloorn/2floor-2$ and maximum degree at most $lfloorn/2floor+1$. We conjecture that the complete balanced bipartite graph maximizes $$ and have verified this computationally for all graphs on at most $10$ vertices.

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

Recommendations

• Nordhaus-Gaddum inequalities for domination in graphs
• Nordhaus-Gaddum bounds for total domination
• Nordhaus-Gaddum bounds for upper total domination
• scientific article; zbMATH DE number 2188609
• Nordhaus--Gaddum bounds for independent domination
• Nordhaus-Gaddum results for the convex domination number of a graph
• A Nordhaus-Gaddum-type result for the 2-domination number
• Nordhaus-Gaddum bounds for domination sums of graphs with minimum degree at least two or three
• Inequalities of Nordhaus-Gaddum type for doubly connected domination number
• Nordhaus-Gaddum results for weakly convex domination number of a graph

zbMATH Keywords

dominating setsNordhaus-Gaddum inequalities

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• Nordhaus-Gaddum inequalities for domination in graphs
• Graphs with few total dominating sets
• Extremal regular graphs: independent sets and graph homomorphisms
• A note on the number of dominating sets of a graph
• Majorization and the minimum number of dominating sets
• Title not available (Why is that?)

Cited In (2)

• A note on the number of dominating sets of a graph
• Title not available (Why is that?)

This page was built for publication: Toward a Nordhaus-Gaddum inequality for the number of dominating sets

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