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

Keough, Lauren; Shane, David

doi:10.2140/involve.2019.12.1175

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

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

Lauren Keough and David Shane

Vol. 12 (2019), No. 7, 1175–1181

DOI: 10.2140/involve.2019.12.1175

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 inequalities relate a graph $G$ to its complement $\bar{G}$ . In this spirit Wagner proved that any graph $G$ on $n$ vertices satisfies $\partial (G) + \partial (\bar{G}) \geq 2^{n}$ , where $\partial (G)$ is the number of dominating sets in a graph $G$ . In the same paper he commented that proving an upper bound for $\partial (G) + \partial (\bar{G})$ among all graphs on $n$ vertices seems to be much more difficult. Here we prove an upper bound on $\partial (G) + \partial (\bar{G})$ and prove that any graph maximizing this sum has minimum degree at least $⌊ n ∕ 2 ⌋ - 2$ and maximum degree at most $⌈ n ∕ 2 ⌉ + 1$ . We conjecture that the complete balanced bipartite graph maximizes $\partial (G) + \partial (\bar{G})$ and have verified this computationally for all graphs on at most $10$ vertices.

Keywords

Nordhaus–Gaddum inequalities, dominating sets

Mathematical Subject Classification 2010

Primary: 05C35, 05C69

Milestones

Received: 5 December 2018

Revised: 18 March 2019

Accepted: 21 March 2019

Published: 12 October 2019

Communicated by Kenneth S. Berenhaut

Authors

Lauren Keough
Department of Mathematics Grand Valley State University Allendale, MI United States

David Shane
Michigan State University East Lansing, MI United States

Vol. 12, No. 7, 2019