Secure domination critical graphs

被引：23

作者：

Grobler, P. J. P. ^{[2
]}

Mynhardt, C. M. ^{[1
]}

机构：

[1] Univ Victoria, Dept Math & Stat, Victoria, BC V8W 3R4, Canada

[2] Univ Stellenbosch, Dept Math Sci, ZA-7602 Matieland, South Africa

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 19期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Secure domination; Protection of a graph; Edge-removal-critical graph; ER-critical graph; ROMAN-EMPIRE; PROTECTION; TREES;

D O I：

10.1016/j.disc.2008.05.050

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A Secure dominating set X of a graph G is a dominating set with the property that each vertex u is an element of V-G - X is adjacent to a vertex nu is an element of X such that (X - {nu}) U {u} is dominating. The minimum cardinality of such a set is called the secure domination number, denoted by gamma(s)(G). We are interested in the effect of edge removal on gamma(s)(G), and characterize gamma(s) ER-critical graphs, i.e. graphs for which gamma(s)(G - e) > gamma(s)(G) for any edge e of G, bipartite gamma(s)-ER-critical graphs and gamma(s)-ER-critical trees. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：5820 / 5827

页数：8

共 18 条

[1] Benecke S, 2006, UTILITAS MATHEMATICA, V71, P161
[2] BENECKE S, 2004, THESIS U STELLENBOSC
[3] Burger A. P., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V49, P159
[4] Burger A. P., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V50, P179
[5] Irredundance, secure domination and maximum degree in trees
Cockayne, E. J.
[J]. DISCRETE MATHEMATICS, 2007, 307 (01) : 12 - 17
[6] Cockayne E. J., 2003, Bulletin of the Institute of Combinatorics and its Applications, V39, P87
[7] Cockayne EJ, 2005, UTILITAS MATHEMATICA, V67, P19
[8] Roman domination in graphs
Cockayne, EJ
Dreyer, PA
Hedetniemi, SM
Hedetniemi, ST
[J]. DISCRETE MATHEMATICS, 2004, 278 (1-3) : 11 - 22
[9] Goddard W., 2005, J. Combin. Math. Combin. Comput., V52, P169
[10] GROBLER PJP, 1999, THESIS U S AFRICA S

← 1 2 →