Bounds on the maximum number of minimum dominating sets

被引：12

作者：

Connolly, Samuel ^{[1
]}

Gabor, Zachary ^{[2
]}

Godbole, Anant ^{[3
]}

Kay, Bill ^{[4
]}

Kelly, Thomas ^{[5
]}

机构：

[1] Brown Univ, Providence, RI 02912 USA

[2] Haverford Coll, Haverford, PA 19041 USA

[3] E Tennessee State Univ, Johnson City, TN 37614 USA

[4] Emory Univ, Atlanta, GA 30322 USA

[5] Univ Waterloo, Waterloo, ON N2L 3G1, Canada

来源：

DISCRETE MATHEMATICS | 2016年 / 339卷 / 05期

基金：

美国国家科学基金会;

关键词：

Dominating sets; Domination number;

D O I：

10.1016/j.disc.2015.12.030

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a graph with domination number gamma, we find bounds on the maximum number of minimum dominating sets. First, for gamma >= 3, we obtain lower bounds on the number of gamma-sets that do not dominate a graph on n vertices. Then, we show that gamma-fold lexicographic product of the complete graph on n(1/gamma) vertices has domination number gamma and ((n)(gamma)) - O(n(gamma-1/gamma)) dominating sets of size gamma. Finally, we see that a certain random graph has, with high probability, (i) domination number gamma; and (ii) all but o(n(gamma)) of its gamma-sets being dominating. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：1537 / 1542

页数：6