A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge con...A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge connectivity, and is denoted by λ′(G). Let ξ(G) bethe minimum edge degree of graph G. It is known that λ′(G) ≤ξ(G) if G contains restrictededge cuts. Graph G is called maximal restricted edge connected if the equality holds in thethe preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to bemaximal restricted edge connected if n ≥ 2.展开更多
Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graph...Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graphs have many good properties such as constant degree, low congestion and optimal diameter. Due to the complexity in topology maintenance, however, to date there have been no effective P2P networks that are proposed based on Kautz graphs with base ~ 2. To address this problem, this paper presents the ＂distributed Kautz （D-Kautz） graphs＂, which adapt Kautz graphs to the characteristics of P2P networks. Using the D-Kautz graphs we further propose SKY, the first effective P2P network based on Kautz graphs with arbitrary base. The effectiveness of SKY is demonstrated through analysis and simulations.展开更多
The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proo...The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.展开更多
This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and con...This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and connects many such clusters by means of a Kautz digraph at the cost of only one additional arc being added to any node in each Mobius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topo- logical properties of Mobius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communi- cation. Additionally, KMcube provides other attractive prop- erties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Mobius-like graphs with the similar diameter to a Mobius cube. Moreover, other hybrid graphs of Kautz digraph and Mobius cubes are proposed and compared.展开更多
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.展开更多
基金Supported by the NNSF of China(10271105) Supported by the NSF of Fujian EducationMinistry(JA03145) Supported by the NNSF of China(10071080)
文摘A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge connectivity, and is denoted by λ′(G). Let ξ(G) bethe minimum edge degree of graph G. It is known that λ′(G) ≤ξ(G) if G contains restrictededge cuts. Graph G is called maximal restricted edge connected if the equality holds in thethe preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to bemaximal restricted edge connected if n ≥ 2.
基金Supported partially by the National Natural Science Foundation of China (Grant Nos. 60673167 and 60703072)the Hunan Provincial Natural Science Foundation of China (Grant No. 08JJ3125)the National Basic Research Program of China (973) (Grant No. 2005CB321801)
文摘Many proposed P2P networks are based on traditional interconnection topologies. Given a static topology, the maintenance mechanism for node join/departure is critical to designing an efficient P2P network. Kautz graphs have many good properties such as constant degree, low congestion and optimal diameter. Due to the complexity in topology maintenance, however, to date there have been no effective P2P networks that are proposed based on Kautz graphs with base ~ 2. To address this problem, this paper presents the ＂distributed Kautz （D-Kautz） graphs＂, which adapt Kautz graphs to the characteristics of P2P networks. Using the D-Kautz graphs we further propose SKY, the first effective P2P network based on Kautz graphs with arbitrary base. The effectiveness of SKY is demonstrated through analysis and simulations.
基金by ANSF( 0 1 0 4 61 0 2 ) and the National Natural Science Foundatim of China ( 1 0 2 71 1 1 4)
文摘The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.
基金This work was partially supported by the National Natural Science Foundation of China （Grant Nos. 61170284, 60903206, 61070216, and 71071160）, the China Postdoctoral Science Foundation （20100480898 and 201104439）, the Science Study Foundation of Doctorial Subject for High Schools （20114307110011）, the Hunan Provincial Innova- tion Foundation for Postgraduate （CX2010B022）, and the NUDT Innovation Foundation for Postgraduate （B100501）.
文摘This paper introduces a novel interconnection network called KMcube （Kautz-Mobius cube）. KMcube is a compound graph of a Kautz digraph and M/Sbius cubes. That is, it uses the Mobius cubes as the unit cluster and connects many such clusters by means of a Kautz digraph at the cost of only one additional arc being added to any node in each Mobius cubes. The topological benefits of both basic graphs are preserved in the compound network. It utilizes the topo- logical properties of Mobius cubes to conveniently embed parallel algorithms into each cluster and the short diameter of a Kautz digraph to support efficient inter-cluster communi- cation. Additionally, KMcube provides other attractive prop- erties, such as the regularity, symmetry, and expandability. The proposed methodology for KMcube is further applied to the compound graphs of Kautz digraph and other Mobius-like graphs with the similar diameter to a Mobius cube. Moreover, other hybrid graphs of Kautz digraph and Mobius cubes are proposed and compared.
基金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.
