China
Africa
Explore chapters and articles related to this topic
Algebraic Signed Graphs: A Review
Published in N. P. Shrimali, Nita H. Shah, Recent Advancements in Graph Theory, 2020
In 1878, Cayley [9] introduced the first algebraic graph called the Cayley graph associated with an algebraic structure ‘group’, which is an important concept relating two different branches of mathematics group theory and graph theory. The Cayley graphs are frequently used to render the abstract structure of a group easily visible by way of representing this structure in graph form. The following definition was given by Cayley [9]: Let H be a finite group and let S⊆ H be a subset. The Cayley graph, denoted by C(H, S) has vertex set H and two distinct vertices x, y ∈ H are joined by a directed edge from x to y if and only if there exists s ∈ S such that x = sy. Each edge is labeled to denote that it corresponds to s ∈ S. If Γ is a graph such that there exists a group H and generating set S ⊂ H with G ≅ C(H, S), then Γ is said to be Cayley.If H=Z4 and S = {1, 3}, then C(H, S) is the cycle on ‘n’ vertices.
NoC Topology
Published in Marcello Coppola, Miltos D. Grammatikakis, Riccardo Locatelli, Giuseppe Maruccia, Lorenzo Pieralisi, Design of Cost-Efficient Interconnect Processing Units, 2020
Marcello Coppola, Miltos D. Grammatikakis, Riccardo Locatelli, Giuseppe Maruccia, Lorenzo Pieralisi
Most constant degree topologies discussed in this Section can be derived from the well known family of Cayley graphs. This rich family of graphs can be used to generate small degree, low diameter networks. Cayley graphs are based on algebraic group theory, e.g. the N-node permutation group with composition operator, or integer with add/multiply operator. Nodes of the Cayley graph are all group elements, while edges (and therefore routing) are based on applying the group operator function (called generator, ⊗), i.e. node x connects to node y, if and only if x ⊗ γi, =y for some γi, ∈ S. Cayley graphs share many nice topological properties. For example, all Cayley graphs are vertex symmetric, and many are also edge-symmetric if all operator pairs are related through a group automorphism. Moreover, almost all Cayley graphs are Hamiltonian, and many are hierarchically recursive and optimally fault tolerant.
The Restricted Congruences Toolbox
Published in Khodakhast Bibak, Restricted Congruences in Computing, 2020
Let Γ be a group, written additively, and S be a finite symmetric subset of Γ that does not contain the identity element of Γ. The Cayley graph of Γ with respect to S, denoted by G = Cay(Γ, S), is the graph whose vertex set is Γ and such that u ∼ v if and only if v − u ∈ S. Note that the Cayley graph G = Cay(Γ, S) is undirected, simple, |S|-regular, and vertex-transitive. Also, G is connected if and only if S generates Γ.
On the g-component connectivity of hypercube-like networks
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Shanshan Yin, Liqiong Xu, Zhecheng Yu
Given a finite group G and a subset such that , where e is the identity element of G, the Cayley graph Cay on G with respect to S is defined to have vertex set G and edge set .