Global defensive alliances in the lexicographic product of paths and cycles

A set S of vertices of a graph G is a defensive alliance of G if for every v∈S, it holds |N[v]∩S|≥|N[v]−S|. An alliance is global if it is also a dominating set. The global defensive alliance number of G is the cardinality of a minimum global defensive alliance set of G. The lexicographic product of...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-09, Vol.283, p.168-188
Main Authors: Barbosa, Rommel M., Dourado, Mitre C., da Silva, Leila R.S.
Format: Article
Language:English
Subjects:
Apexes
Cycle
Global defensive alliance
Graph theory
Lexicographic product
Path
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set S of vertices of a graph G is a defensive alliance of G if for every v∈S, it holds |N[v]∩S|≥|N[v]−S|. An alliance is global if it is also a dominating set. The global defensive alliance number of G is the cardinality of a minimum global defensive alliance set of G. The lexicographic product of graphs Gn=(V1,E1) and Hm=(V2,E2) is the graph G=(V,E), such that V=V1×V2 and E={(u1,u2)(v1,v2):u1v1∈E1, or u1=v1 and u2v2∈E2}. In this paper, we determine the global defensive alliance number of the lexicographic product of paths and cycles.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2019.12.024