Inequalities of Nordhaus-Gaddum type for doubly connected domination number

被引：6

作者：

Akhbari, M. H.

Hasni, R.

Favaron, O.

Karami, H.

Sheikholeslami, S. M. ^{[1
]}

机构：

[1] Univ Sci Malaysia, Sch Math Sci, George Town 11800, Malaysia

来源：

DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 14期

关键词：

Doubly connected dominating set; Doubly connected domination number; Nordhaus-Gaddum inequalities;

D O I：

10.1016/j.dam.2010.04.011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V - S are connected. The doubly connected domination number gamma(cc) (G) is the minimum size of such a set. We prove that when G and (G) over bar are both connected of order n, gamma(cc) (G) + gamma(cc) ((G) over bar) <= n + 3 and we describe the two infinite families of extremal graphs achieving the bound. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：1465 / 1470

页数：6