On global (strong) defensive alliances in some product graphs

	On global (strong) defensive alliances in some product graphs
Article 3, Volume 2, Issue 1, Winter and Spring 2017, Page 21-33 PDF (441 K)
Document Type: Original paper
DOI: 10.22049/cco.2017.13595
Authors
Ismael Gonzalez Yero ¹; Marko Jakovac²; Dorota Kuziak³
¹University of Cadiz
²University of Maribor
³Universitat Rovira i Virgili
Abstract
A defensive alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at most one more neighbor outside of $S$ than it has inside of $S$. A defensive alliance $S$ is called global if it forms a dominating set. The global defensive alliance number of a graph $G$ is the minimum cardinality of a global defensive alliance in $G$. In this article we study the global defensive alliances in Cartesian product graphs, strong product graphs and direct product graphs. Specifically we give several bounds for the global defensive alliance number of these graph products and express them in terms of the global defensive alliance numbers of the factor graphs.
Keywords
Defensive alliances; global defensive alliances; Cartesian product graphs; strong product graph; direct product graphs
Main Subjects
Graph theory


Statistics Article View: 685 PDF Download: 630