The (strong) rainbow connection numbers of Cayley graphs on Abelian groups

A path in an edge-colored graph G, whose adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. The strong rainbow connection number src(G) of G is the minimum integer i for which there exists an i-edge-coloring of G such that every two distinct vertices u and v of G are connected by a rainbow path of length d(u,v). In this paper, we give upper and lower bounds of the (strong) rainbow connection numbers of Cayley graphs on Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases.     

One conjecture of bubble-sort graphs

The bubble-sort graph is an important interconnection network designed from Cayley graph model. One conjecture is proposed in Shi and Lu (2008) [10] as follows: for any integer n?2, if n is odd then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles and its perfect matching that has no edges in common with the hamiltonian cycles. In this paper, we prove that conjecture is true for n=5,6.     

A New Family of Interconnection Networks of Fixed Degree Three

A new family of interconnection networks WGn is proposed, that is constant degree 3 Cayley graph, and is isomorphic to a Cayley graph of the wreath product Z2 Sn when the generator set is chosen properly. Its different algebraic properties is investigated and a routing algorithm is given with the diameter upper bounded by 3n2 - 6n 4. The embedding properties and the fault tolerance are devired. In conclusion, we present a comparison of some familiar networks with constant degree 3.     

The pessimistic diagnosability of alternating group graphs under the PMC model

The process of identifying faulty processors is called the diagnosis of the system. Several diagnostic models have been proposed, the most popular is the PMC (Preparata, Metze and Chen) diagnostic model. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty nodes within a set containing at most one fault-free node. A system is t/t$t/t$-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G  , denoted by _tp(G)$t_p(G)$, is the maximal number of faulty processors so that the system G   is t/t$t/t$-diagnosable. Jwo et al. [11] introduced the alternating group graph as an interconnection network topology for computing systems. The proposed graph has many advantages over hypercubes and star graphs. For example, for all alternating group graphs, every pair of vertices in the graph are connected by a Hamiltonian path and the graph can embed cycles with arbitrary length with dilation 1. In this article, we completely determine the pessimistic diagnosability of an n  -dimensional alternating group graph, denoted by _AGn${\mathit{AG}}_n$. Furthermore, _tp(_AGn)=4n−11$t_p({\mathit{AG}}_n)=4n-11$ for n≥4$n\ge 4$.     

Embedding Hamiltonian cycles in alternating group graphs under conditional fault model

In this paper, assuming that each node is incident with two or more fault-free links, we show that an n-dimensional alternating group graph can tolerate up to 4n − 13 link faults, where n ? 4, while retaining a fault-free Hamiltonian cycle. The proof is computer-assisted. The result is optimal with respect to the number of link faults tolerated. Previously, without the assumption, at most 2n − 6 link faults can be tolerated for the same problem and the same graph.     

A channel assignment problem for optical networks modelled by Cayley graphs

A problem arising from a recent study of scalability of optical networks seeks to assign channels to the vertices of a network so that vertices distance 2 apart receive distinct channels. In this paper we introduce a general channel assignment scheme for Cayley graphs on abelian groups, and derive upper bounds for the minimum number of channels needed for such graphs. As application we give a systematic way of producing near-optimal channel assignments for connected graphs admitting a vertex-transitive abelian group of automorphisms. Hypercubes are examples of such graphs, and for them our near-optimal upper bound gives rise to the one obtained recently by Wan.     

极小Cayley图的确定性小世界网络模型

小世界网络的确定性模型研究是复杂网络建模领域的重要分支,通过分析Cayley图的极小性与小世界特性的关联,提出一种基于极小Cayley图构造小世界网络的确定性模型．模型通过选择满足条件的极小Cayley图,恰当地扩展其生成集,构造出一类对称性强且结构规则的小世界网络．结果表明, 和现有模型不同,该模型可根据需求构造常数度或非常数度网络,且生成网络不仅具有较高的聚集系数和低的网络直径,而且是节点对称的,在通信网络、结构化P2P覆盖网络等实际领域的拓扑结构设计中具有重要应用．     

BuNet：一种基于Cayley图的覆盖网络*

为了构建一个具有路由表小、查询路径长度短、鲁棒性强且支持文件组浏览服务的P2P覆盖网络，通过对扩展蝶网理论的分析与设计，提出了一个新的基于Cayley图的结构化P2P网络BuNet。通过模拟实验，证明了BuNet相比其他结构化P2P网络在查询路径短和鲁棒性等方面具有更好的性能。     

Cayley graphs as models of deterministic small-world networks

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.