Twin domination in generalized Kautz digraphs  

作　　者：董艳侠 单而芳 吴领叶 

机构地区：[1]Department of Mathematics,College of Sciences,Shanghai University

出　　处：《Journal of Shanghai University(English Edition)》2010年第3期177-181,共5页上海大学学报（英文版）

基　　金：Project supported by the National Natural Science Foundation of China (Grant Nos.10571117, 60773078);the Shuguang Plan of Shanghai Education Development Foundation (Grant No.06SG42);the Shanghai Leading Academic Discipline Project(Grant No.J50101)

摘　　要：Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.

关 键 词：twin dominating set generalized Kuatz digraph interconnection networks 

分 类 号：O157.5[理学—数学] TK24[理学—基础数学]