Maximum number of minimum dominating and minimum total dominating sets

Authors Anant P. Godbole, Jessie D. Jamieson, William Jamieson

Publication date 28 August 2014

Published in Utilitas Mathematica (Search for Journal in Brave)

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

domination number extremal graphs total domination number

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

Abstract: Given a connected graph with domination (or total domination) number gamma>=2, we ask for the maximum number m_gamma and m_{gamma,T} of dominating and total dominating sets of size gamma. An exact answer is provided for gamma=2and lower bounds are given for gamma>=3.

Review text

Given a connected graph of order \(n\) and domination or total domination number \(\gamma\), the paper considers the problem of determining the maximum number of minimum (total) dominating sets. The problem is solved for \(\gamma = 2\) for the domination number and for the total domination number. For larger \(\gamma\), a construction is given that yields a non-trivial lower bound for the domination number.

Recommendations

Cited in

(8)

This page was built for publication: Maximum number of minimum dominating and minimum total dominating sets

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