Alliance Free and Alliance Cover Sets

A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not cont...

Full description

Saved in:
Bibliographic Details
Published in:Acta mathematica Sinica. English series 2011-03, Vol.27 (3), p.497-504
Main Authors: Rodriguez-Velazquez, Juan Alberto, Sigarreta, José María, Gonzalez Yero, Ismael, Bermudo, Sergio
Format: Article
Language:English
Subjects:
Boundaries
Mathematical analysis
Mathematics
Mathematics and Statistics
Studies
大肠杆菌
工程兵
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.
ISSN:1439-8516
1439-7617
DOI:10.1007/s10114-011-0056-1