On the complement graph and defensive k-alliances

被引：20

作者：

Sigarreta, J. M. ^{[2
]}

Bermudo, S. ^{[1
]}

Fernau, H. ^{[3
]}

机构：

[1] Pablo Olavide Univ, Dept Econ Quantitat Methods & Econ Hist, Seville 41013, Spain

[2] Autonomous Univ Guerrero, Fac Math, Acapulco, Guerrero, Mexico

[3] Univ Trier, Abt Informat, Fachbereich 4, D-54286 Trier, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 08期

关键词：

Defensive alliances; Complement graph; Domination number; Independent set; NP-completeness;

D O I：

10.1016/j.dam.2008.12.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we obtain several tight bounds of the defensive k-alliance number in the complement graph from other parameters of the graph. In particular, we investigate the relationship between the alliance numbers of the complement graph and the minimum and maximum degree, the domination number and the isoperimetric number of the graph. Moreover, we prove the NP-completeness of the decision problem underlying the defensive k-alliance number. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：1687 / 1695

页数：9

共 13 条

[1]

[Anonymous], 1996, Introduction to the Theory of Computation

[2]

[Anonymous], 2003, Bulletin of the Institute of Combinatorics and its Applications

[3]

Cami A., 2006, Journal of Combinatorial Mathematics and Combinatorial Computing, V58, P23

[4]

Carvajal R, 2007, LECT NOTES COMPUT SC, V4708, P218

[5]

Duchet P., 1982, North-Holland Math. Stud., V62, P71, DOI DOI 10.1016/S0304-0208(08)73549-7

[6]

Flake G. W., 2000, Proceedings. KDD-2000. Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, P150, DOI 10.1145/347090.347121

[7] A quantitative analysis of secondary RNA structure using domination based parameters on trees [J].

Haynes, T ;

Knisley, D ;

Seier, E ;

Zou, Y .

BMC BIOINFORMATICS, 2006, 7 (1)

[8]

Haynes TW, 2003, ELECTRON J COMB, V10

[9]

Kristiansen P., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V48, P157

[10] Laplacian eigenvalues and partition problems in hypergraphs [J].

Rodriguez, J. A. .

APPLIED MATHEMATICS LETTERS, 2009, 22 (06) :916-921

← 1 2 →