Counting the Number of Weakly Connected Dominating Sets of Graphs

被引：0

作者：

Alikhani, Saeid ^{[1
]}

Jahari, Somayeh ^{[1
]}

Mehryar, Mohammad ^{[1
]}

机构：

[1] Yazd Univ, Dept Math, Yazd, Iran

来源：

MALAYSIAN JOURNAL OF MATHEMATICAL SCIENCES | 2016年 / 10卷 / 03期

关键词：

Dominating sets; Weakly connected; Path; Cycle;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G = (V(G); E(G)) be a simple graph. A non-empty set S subset of V (G) is a weakly connected dominating set in G, if the subgraph obtained from G by removing all edges each joining any two vertices in V (G) backslash S is connected. In this paper, we consider some graphs and study the number of their weakly connected dominating sets.

引用

页码：297 / 306

页数：10

共 50 条

[31] The second largest number of maximal independent sets in connected graphs with at most one cycle [J].

Jou, Min-Jen .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 24 (03) :192-201

[32] On the number of minimal dominating sets on some graph classes [J].

Couturier, Jean-Francois ;

Letourneur, Romain ;

Liedloff, Mathieu .

THEORETICAL COMPUTER SCIENCE, 2015, 562 :634-642

[33] Locating-dominating sets in twin-free graphs [J].

Foucaud, Florent ;

Henning, Michael A. ;

Loewenstein, Christian ;

Sasse, Thomas .

DISCRETE APPLIED MATHEMATICS, 2016, 200 :52-58

[34] Message ferries as generalized dominating sets in intermittently connected mobile networks [J].

Polat, Bahadir K. ;

Sachdeva, Pushkar ;

Ammar, Mostafa H. ;

Zegura, Ellen W. .

PERVASIVE AND MOBILE COMPUTING, 2011, 7 (02) :189-205

[35] Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm [J].

Samir Khuller ;

Sheng Yang .

Algorithmica, 2019, 81 :2592-2605

[36] Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm [J].

Khuller, Samir ;

Yang, Sheng .

ALGORITHMICA, 2019, 81 (06) :2592-2605

[37] The number of maximum independent sets in graphs [J].

Jou, MJ ;

Chang, GJ .

TAIWANESE JOURNAL OF MATHEMATICS, 2000, 4 (04) :685-695

[38] On the construction of k-connected m-dominating sets in wireless networks [J].

Yingshu Li ;

Yiwei Wu ;

Chunyu Ai ;

Raheem Beyah .

Journal of Combinatorial Optimization, 2012, 23 :118-139

[39] What Can Be Approximated Locally? Case Study: Dominating Sets in Planar Graphs [J].

Lenzen, Christoph ;

Oswald, Yvonne Anne ;

Wattenhofer, Roger .

SPAA'08: PROCEEDINGS OF THE TWENTIETH ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2008, :46-54

[40] TS-Reconfiguration of Dominating Sets in Circle and Circular-Arc Graphs [J].

Bousquet, Nicolas ;

Joffard, Alice .

FUNDAMENTALS OF COMPUTATION THEORY, FCT 2021, 2021, 12867 :114-134

← 1 2 3 4 5 →