Global defensive alliances of trees and Cartesian product of paths and cycles

CCUR > College of Business > Department of Information Management & Graduate Institute of Information Management > periodical articles > Item 987654321/24276

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/24276

Title:	Global defensive alliances of trees and Cartesian product of paths and cycles
Authors:	ang, CW (Chang, Chan-Wei) Chia, ML (Chia, Ma-Lian) Hsu, CJ (Hsu, Cheng-Ju) Kuo, D (Kuo, David) Lai, LL (Lai, Li-Ling) Wang, FH (Wang, Fu-Hsing)
Contributors:	Dept Informat Management
Keywords:	Global defensive alliance Tree Cartesian product Path Cycle
Date:	2012-03
Issue Date:	2013-02-22 14:38:53 (UTC+8)
Abstract:	Given a graph G. a defensive alliance of G is a set of vertices S subset of V(G) satisfying the condition that for each v epsilon S. at least half of the vertices in the closed neighborhood of v are in S. A defensive alliance S is called global if every vertex in V(G) - S is adjacent to at least one member of the defensive alliance S. The global defensive alliance number of G. denoted gamma(a)(G), is the minimum size around all the global defensive alliances of G. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete k-ary trees for k = 2, 3, 4. We also establish upper bounds and lower bounds for gamma(a)(P-m x P-n), gamma(a)(C-m x P-n) and gamma(a)(C-m x C-n), and show that the bounds are sharp for certain m, n. (c) 2011 Elsevier B.V. All rights reserved.
Relation:	DISCRETE APPLIED MATHEMATICS 卷: 160 期: 4-5 頁數: 479-487
Appears in Collections:	[Department of Information Management & Graduate Institute of Information Management] periodical articles

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	478	View/Open

View Licence

Loading...