On graphs for which the connected domination number is at most the total domination number

被引：11

作者：

Schaudt, Oliver ^{[1
]}

机构：

[1] Univ Cologne, Inst Informat, D-50931 Cologne, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 7-8期

关键词：

Connected domination; Total domination; Paired-domination; Perfection of parameters; SUBGRAPHS;

D O I：

10.1016/j.dam.2011.12.025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this note, we give a finite forbidden subgraph characterization of the connected graphs for which any non-trivial connected induced subgraph has the property that the connected domination number is at most the total domination number. This question is motivated by the fact that any connected dominating set of size at least 2 is in particular a total dominating set. It turns out that in this characterization, the total domination number can equivalently be substituted by the upper total domination number, the paired-domination number and the upper paired-domination number, respectively. Another equivalent condition is given in terms of structural domination. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：1281 / 1284

页数：4