Narrow Results

Homogeneous multiprocessor systems are usually modelled by undirected graphs. Vertices of these graphs represent the processors, while edges denote the connection links between adjacent processors. Let G be a graph with diameter D, maximum vertex degree Δ, the largest eigenvalue λ₁ and m distinct eigenvalues. The products mΔ and (D+1)λ₁ are called the tightness of G of the first and second type, respectively. In recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. In a previous paper we studied these and some other types of tightness and some related graph invariants and demonstrated their usefulness in the analysis of multiprocessor interconnection networks. We proved that the number of connected graphs with a bounded tightness is finite. In this paper we determine explicitly graphs with tightness values not exceeding 9. There are 69 such graphs and they contain up to 10 vertices. In addition we identify graphs with minimal tightness values when the number of vertices is n = 2,…, 10.

We discuss nearest neighbor load balancing schemes on processor networks which are represented by a cartesian product of graphs and present a new optimal diffusion scheme for general graphs. In the first part of the paper, we introduce the Alternating-Direction load balancing scheme, which reduces the number of load balance iterations by a factor of 2 for cartesian products of graphs. The resulting flow is theoretically analyzed and can be very high for certain cases. Therefore, we further present the Mixed-Direction scheme which needs the same number of iterations but computes in most cases a much smaller flow. In the second part of the paper, we present a simple optimal diffusion scheme for general graphs, calculating a balancing flow which is minimal in the l₂ norm. It is based on the spectra of the graph representing the network and needs only m-1 iterations to balance the load with m being the number of distinct eigenvalues. Known optimal diffusion schemes have the same performance, however the optimal scheme presented in this paper can be implemented in a very simple manner. The number of iterations of optimal diffusion schemes is independent of the load scenario and, thus, they are practical for networks which represent graphs with known spectra. Finally, our experiments exhibit that the new optimal scheme can successfully be combined with the Alternating-Direction and Mixed-Direction schemes for efficient load balancing on product graphs.

Let $G$ be a group and $S$ an inverse closed subset of $G\setminus \{1\}$. By a Cayley graph $\mathrm{\text{Cay}}(G,S)$, we mean the graph whose vertex set is the set of elements of $G$ and two vertices $x$ and $y$ are adjacent if $x^{-1}y\in S$. A group $G$ is called a CI-group if $\mathrm{\text{Cay}}(G,S)\cong \mathrm{\text{Cay}}(G,T)$ for some inverse closed subsets $S$ and $T$ of $G\setminus \{1\}$, then $S^{\alpha }=T$ for some automorphism $\alpha$ of $G$. A finite group $G$ is called a BI-group if $\mathrm{\text{Cay}}(G,S)\cong \mathrm{\text{Cay}}(G,T)$ for some inverse closed subsets $S$ and $T$ of $G\setminus \{1\}$, then $M_{\nu }^S=M_{\nu }^T$ for all positive integers $\nu$, where $M_{\nu }^S$ denotes the set $\{{\sum }_{s\in S}\chi (s)|\chi (1)=\nu ,\chi \text{ is a complex irreducible character of }G\}$. It was asked by László Babai [Spectra of Cayley graphs, J. Combin. Theory Ser. B27 (1979) 180–189] if every finite group is a BI-group; various examples of finite non-BI-groups are presented in [A. Abdollahi and M. Zallaghi, Character sums of Cayley graph, Comm. Algebra43(12) (2015) 5159–5167]. It is noted in the latter paper that every finite CI-group is a BI-group and all abelian finite groups are BI-groups. However, it is known that there are finite abelian non-CI-groups. Existence of a finite non-abelian BI-group which is not a CI-group is the main question which we study here. We find two non-abelian BI-groups of orders 20 and 42 which are not CI-groups. We also list all BI-groups of orders up to 30.