A New Upper Bound on the Global Defensive Alliance Number in Trees

Xue-gang Chen; Wai Chee Shiu

doi:10.37236/689

A New Upper Bound on the Global Defensive Alliance Number in Trees

Xue-gang Chen, Wai Chee Shiu

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

2 Citations (Scopus)

Abstract

A global defensive alliance in a graph G = (V,E) is a dominating set S satisfying the condition that for every vertex v ∈ S, |N[v] ∩ S| ≥ |N(v) ∩ (V - S)|. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.

Original language	English
Article number	P202
Number of pages	7
Journal	Electronic Journal of Combinatorics
Volume	18
Issue number	1
DOIs	https://doi.org/10.37236/689
Publication status	Published - 10 Oct 2011

Scopus Subject Areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

User-Defined Keywords

Global defensive alliance number
Tree
Upper bound

Access to Document

10.37236/689

Cite this

@article{3cd20c93549e4b0ba8c285f443099b62,

title = "A New Upper Bound on the Global Defensive Alliance Number in Trees",

abstract = "A global defensive alliance in a graph G = (V,E) is a dominating set S satisfying the condition that for every vertex v ∈ S, |N[v] ∩ S| ≥ |N(v) ∩ (V - S)|. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.",

keywords = "Global defensive alliance number, Tree, Upper bound",

author = "Xue-gang Chen and Shiu, {Wai Chee}",

year = "2011",

month = oct,

day = "10",

doi = "10.37236/689",

language = "English",

volume = "18",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - A New Upper Bound on the Global Defensive Alliance Number in Trees

AU - Chen, Xue-gang

AU - Shiu, Wai Chee

PY - 2011/10/10

Y1 - 2011/10/10

N2 - A global defensive alliance in a graph G = (V,E) is a dominating set S satisfying the condition that for every vertex v ∈ S, |N[v] ∩ S| ≥ |N(v) ∩ (V - S)|. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.

AB - A global defensive alliance in a graph G = (V,E) is a dominating set S satisfying the condition that for every vertex v ∈ S, |N[v] ∩ S| ≥ |N(v) ∩ (V - S)|. In this note, a new upper bound on the global defensive alliance number of a tree is given in terms of its order and the number of support vertices. Moreover, we characterize trees attaining this upper bound.

KW - Global defensive alliance number

KW - Tree

KW - Upper bound

UR - http://www.scopus.com/inward/record.url?scp=80054701760&partnerID=8YFLogxK

U2 - 10.37236/689

DO - 10.37236/689

M3 - Journal article

AN - SCOPUS:80054701760

SN - 1077-8926

VL - 18

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P202

ER -

A New Upper Bound on the Global Defensive Alliance Number in Trees

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this