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-λ.展开更多
Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley g...Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D2n are optimal super-λ. The number Ni（G） of cutsets of size i, λ≤ i≤λ＇ is given as Ni（G） = n[^（n-1）δ i-δ].展开更多
Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum siz...Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.展开更多
The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;...The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;1,2,.:,k)is equal to n/2 for 2≤h≤n/2,k=2 and n iseven,andλ_(h)(D)=g(k-1)for 2<h≤g and 3≤k≤n/2,where g is the girth of D.As consequences,the super restricted arc-connectedness of Harary digraph D is obtained immediately.In particular,for k=2 and n is even or 3≤k<n/2and n can be divided by k,it can be determined that distinct positive(respectively,negative)Ah-superatoms of D are vertex disjoint for 2≤h≤g.展开更多
文摘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-λ.
基金Supported by the National Key Basic Research and Development (973) Program of China(No. 2007CB311003)
文摘Cayley graphs have many good properties as models of communication networks. This study analyzes the reliability of the Cayley graph based on the dihedral graph. Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D2n are optimal super-λ. The number Ni（G） of cutsets of size i, λ≤ i≤λ＇ is given as Ni（G） = n[^（n-1）δ i-δ].
基金supported by National Natural Science Foundation of China(Grant No.61073046)
文摘Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.
基金the National Natural Science Foundation of China(No.11531011).
文摘The h-restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the h-restricted arc-connectivity of the Harary digraph D=G(n;1,2,.:,k)is equal to n/2 for 2≤h≤n/2,k=2 and n iseven,andλ_(h)(D)=g(k-1)for 2<h≤g and 3≤k≤n/2,where g is the girth of D.As consequences,the super restricted arc-connectedness of Harary digraph D is obtained immediately.In particular,for k=2 and n is even or 3≤k<n/2and n can be divided by k,it can be determined that distinct positive(respectively,negative)Ah-superatoms of D are vertex disjoint for 2≤h≤g.
