Vol. 12, No. 7, 2019

Download this article
Download this article For screen
For printing
Recent Issues

Volume 17
Issue 2, 183–362
Issue 1, 1–182

Volume 16, 5 issues

Volume 15, 5 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
Editors' interests
ISSN (electronic): 1944-4184
ISSN (print): 1944-4176
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

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

Nordhaus–Gaddum inequalities, dominating sets
Mathematical Subject Classification 2010
Primary: 05C35, 05C69
Received: 5 December 2018
Revised: 18 March 2019
Accepted: 21 March 2019
Published: 12 October 2019

Communicated by Kenneth S. Berenhaut
Lauren Keough
Department of Mathematics
Grand Valley State University
Allendale, MI
United States
David Shane
Michigan State University
East Lansing, MI
United States