Distance domination of generalized de Bruijn and Kautz digraphs

详细信息    查看全文

• 作者：Yanxia Dong ; Erfang Shan ; Xiao Min
• 关键词：Combinatorial problems ; dominating set ; distance dominating set ; generalized de Bruijn digraph ; generalized Kautz digraph
• 刊名：Frontiers of Mathematics in China
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：12
• 期：2
• 页码：339-357
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics, general;
• 出版者：Higher Education Press
• ISSN：1673-3576
• 卷排序：12

文摘

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of VD is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ_k(G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G_B(n, d) and generalized Kautz digraphs G_K(n, d) are good candidates for interconnection networks. Denote Δ_k:= (∑_j=0kdj)−1. F. Tian and J. Xu showed that ⌈nΔ_k⌉ γ_k(G_B(n, d)) ≤⌈n/dk⌉ and ⌈nΔ_k⌉ ≤ γ_k(G_K(n, d)) ≤ ⌈n/dk⌉. In this paper, we prove that every generalized de Bruijn digraph G_B(n, d) has the distance k-domination number ⌈nΔ_k⌉ or ⌈nΔ_k⌉+1, and the distance k-domination number of every generalized Kautz digraph G_K(n, d) bounded above by ⌈n/(dk−1+dk)⌉. Additionally, we present various sufficient conditions for γ_k(G_B(n, d)) = ⌈nΔ_k⌉ and γ_k(G_K(n, d)) = ⌈nΔ_k⌉.