Let G= （V,A） be adigraph 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 ver...Let G= （V,A） be adigraph 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 V ／ D 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 GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（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 GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].展开更多
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D...The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.展开更多
A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v...A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.展开更多
基金Acknowledgements This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11471210, 11571222, 11601262）.
文摘Let G= （V,A） be adigraph 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 V ／ D 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 GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（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 GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].
基金Supported by the National Natural Science Foundation of China(No.10271114,No.10301031).
文摘The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.
文摘A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.
