A survey on alliances and related parameters in graphs

Henning Fernau, Juan A. Rodriguez-Velazquez


In this paper, we show that several graph parameters are known in different areas under completely different names.
More specifically, our observations connect signed domination, monopolies, $\alpha$-domination, $\alpha$-independence,
positive influence domination,
and a parameter associated to fast information propagation
in networks to parameters related to various notions of global $r$-alliances in graphs.
We also propose a new framework, called (global) $(D,O)$-alliances, not only in order to characterize
various known variants of alliance and domination parameters, but also to suggest a unifying framework for the study of alliances and domination.
Finally, we also give a survey on the mentioned graph parameters, indicating how results transfer due to our observations.


graph parameters; domination in graphs; alliances in graphs; computational complexity of graph problems

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2014.2.1.7


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats