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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 3.12.41.106 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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