The order/degree problem consists of finding the smallest diameter graph for a given order and degree. Such a graph is beneficial for designing low-latency networks with high performance for massively parallel computers. The average shortest path length (ASPL) of a graph has an influence on latency. In this paper, we propose a novel order adjustment approach. In the proposed approach, we search for Cayley graphs of the given degree that are close to the given order. We then adjust the order of the best Cayley graph to meet the given order. For some order and degree pairs, we explain how to derive the smallest known graphs from the Graph Golf 2016 and 2017 competitions.

A vertex subset F ⊆ V(G) is called a cyclic vertex-cut set of a connected graph G if G-F is disconnected such that at least two components in G-F contain cycles. The cyclic vertex connectivity is the cardinality of a minimum cyclic vertex-cut set. In this paper, we show that the cyclic vertex connectivity of the trivalent Cayley graphs TGn is equal to eight for n ≥ 4.

Hypercube Qn is a well-known graph structure having three different kinds of equivalent definitions that are: 1. binary n bit sequences with the adjacency condition, 2. Q1=K2, Qn=Qn-1 K2, where means the Cartesian product, 3. the Cayley graph on Z2n with the generator set {100, 0100, , 001}. We give a necessary and sufficient condition for a set of binary sequences to be a generator set for the hypercube. Then, we give relations between some generator sets and relational products. These results show the wide variety of representability of hypercubes which would be used for many applications.

In this paper, we present a new extension of the butterfly digraph, which is known as one of the topologies used for interconnection networks. The butterfly digraph was previously generalized from binary to d-ary. We define a new digraph by adding a signed label to each vertex of the d-ary butterfly digraph. We call this digraph the dihedral butterfly digraph and study its properties. Furthermore, we show that this digraph can be represented as a Cayley graph. It is well known that a butterfly digraph can be represented as a Cayley graph on the wreath product of two cyclic groups [1]. We prove that a dihedral butterfly digraph can be represented as a Cayley graph in two ways.

In this paper, we study the feedback vertex set problem for trivalent Cayley graphs, and construct a minimum feedback vertex set in trivalent Cayley graphs using the result on cube-connected cycles and the Cayley graph representation of trivalent Cayley graphs.

We propose a new class of binary nonlinear codes of constant weights derived from a permutation representation of a group that is given by a combinatorial definition such as Cayley graphs of a group. These codes are constructed by the following direct interpretation method from a group: (1) take one discrete group whose elements are defined by generators and their relations, such as those in the form of Cayley graphs; and (2) embedding the group into a binary space using some of their permutation representations by providing the generators with realization of permutations of some terms. The proposed codes are endowed with some good characteristics as follows: (a) we can easily learn information about the distances of the obtained codes, and moreover, (b) we can establish a decoding method for them that can correct random errors whose distances from code words are less than half of the minimum distances achieved using only parity checking procedures.

A minimum feedback node set in a graph is a minimum node subset whose deletion makes the graph acyclic. Its detection in a dependency graph is important to recover from a deadlock configuration. A livelock configuration is also avoidable if a check point is set in each node in the minimum feedback node set. Hence, its detection is very important to establish dependable network systems. In this letter, we give a minimum feedback node set in a trivalent Cayley graph. Assuming that each word has n bits, for any node, we can judge if it is included in the set or not in constant time.

In this paper, we investigate self diagnosable systems on multi-processor systems, known as one-step t-diagnosable systems introduced by Preparata et al. Kohda has proposed "highly structured system" to design diagnosable systems such that faulty processors are diagnosed efficiently. On the other hand, it is known that Cayley graphs have been investigated as good models for architectures of large-scale parallel processor systems. We investigate some conditions for Cayley graphs to be topologies for optimal highly structured diagnosable systems, and present several examples of optimal diagnosable systems represented by Cayley graphs.

The trivalent Cayley graph TCn was introduced and investigated in [1],[2]. Though "the diameter" was presented in [2], unfortunately it was not the diameter but an upper bound of it. In this paper, a lower bound of the diameter dia(TCn) of the trivalent Cayley graph TCn is investigated and the formula dia(TCn) = 2n - 2 for n 3 is established.

Dynamical theory of cellular automata on groups is developed. Main results are non-Euclidean extensions of Sato and Honda's results on the dynamics of Euclidean cellular automata. The notion of the period of a configuration is redefined in a more group theoretical way. The notion of a co-finite configuration substitutes the notion of a periodic configuration, where the new term is given to it to reflect and emphasize the importance of finiteness involved. With these extended or substituted notions, the relations among period preservablity, injectivity, and Poisson stability of parallel maps are established. Residually finite groups are shown to give a nice topological property that co-finite configurations are dense in the configuration space.