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

文化大學機構典藏 CCUR > 商學院 > 資訊管理學系暨資訊管理研究所 > 期刊論文 > Item 987654321/24276

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://irlib.pccu.edu.tw/handle/987654321/24276

题名:	Global defensive alliances of trees and Cartesian product of paths and cycles
作者:	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)
贡献者:	Dept Informat Management
关键词:	Global defensive alliance Tree Cartesian product Path Cycle
日期:	2012-03
上传时间:	2013-02-22 14:38:53 (UTC+8)
摘要:	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.
關聯:	DISCRETE APPLIED MATHEMATICS 卷: 160 期: 4-5 頁數: 479-487
显示于类别:	[資訊管理學系暨資訊管理研究所 ] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	483	检视/开启

检视Licence

在CCUR中所有的数据项都受到原著作权保护.