Global alliances and independence in trees

Mustapha Chellali; Teresa W. Haynes

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 19-27
  • ISSN: 2083-5892

Abstract

top
A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.

How to cite

top

Mustapha Chellali, and Teresa W. Haynes. "Global alliances and independence in trees." Discussiones Mathematicae Graph Theory 27.1 (2007): 19-27. <http://eudml.org/doc/270383>.

@article{MustaphaChellali2007,
abstract = {A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.},
author = {Mustapha Chellali, Teresa W. Haynes},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {defensive alliance; offensive alliance; global alliance; domination; trees; independence number},
language = {eng},
number = {1},
pages = {19-27},
title = {Global alliances and independence in trees},
url = {http://eudml.org/doc/270383},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Mustapha Chellali
AU - Teresa W. Haynes
TI - Global alliances and independence in trees
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 19
EP - 27
AB - A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.
LA - eng
KW - defensive alliance; offensive alliance; global alliance; domination; trees; independence number
UR - http://eudml.org/doc/270383
ER -

References

top
  1. [1] M. Blidia, M. Chellali and O. Favaron, Independence and 2-domination in trees, Austral. J. Combin. 33 (2005) 317-327. 
  2. [2] G. Chartrand and L. Lesniak, Graphs & Digraphs: Third Edition (Chapman & Hall, London, 1996). 
  3. [3] E.J. Cockayne, O. Favaron, C. Payan and A.G. Thomason, Contributions to the theory of domination, independence, and irredundance in graphs, Discrete Math. 33 (1981) 249-258, doi: 10.1016/0012-365X(81)90268-5. Zbl0471.05051
  4. [4] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Global defensive alliances in graphs, The Electronic J. Combin. 10 (2003) R47. Zbl1031.05096
  5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  7. [7] S.M. Hedetniemi, S.T. Hedetniemi and P. Kristiansen, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157-177. Zbl1051.05068

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.