Narrow Results

Let $\mathrm{\Gamma }=Cay(G,S)$ be the Cayley graph on the abelian group $G$. The zero forcing number $Z(\mathrm{\Gamma })$ of graph $\mathrm{\Gamma }$ is the minimum of $\left|Z\right|$ over all zero forcing sets $Z\subseteq V(\mathrm{\Gamma })$. In this paper, for cubic connected Cayley graphs $\mathrm{\Gamma }$ on abelian groups $G$, we show that $Z(\mathrm{\Gamma })=3$ or $4$. Moreover, we prove that for quartic connected Cayley graphs $\mathrm{\Gamma }$ on abelian groups $G$ with $G\ncong {\mathbb{Z}}_n$, either $Z(\mathrm{\Gamma })=4,6,7,8$ or $Z(\mathrm{\Gamma })$ is determined by the order of the elements of $S$.

Let $H$ be a group and $S\subseteq H$ be a set of group elements such that the identity element $e\notin S$ and $S=S^{-1}$. The Cayley graph $\mathrm{\text{Cay}}(H,S)$ associated with $(H,S)$ is an undirected graph with a vertex set equal to $H$ and two vertices $g,h\in H$ are adjacent, whenever $g{h}^{-1}\in S$. Let $R$ be a commutative ring with unity. $R^{+}$ and $Z^{\ast }(R)$ are the additive group and the set of all non-zero zero-divisors of $R$, respectively. The symbol $ℂ𝔸𝕐(R)$ denotes the Cayley graph $\mathrm{\text{Cay}}(R^{+},Z^{\ast }(R))$ and $G_R$ represents the unitary Cayley graph $\mathrm{\text{Cay}}(R^{+},U(R))$. In this study, the total domination number, perfect domination number and bondage number for $ℂ𝔸𝕐(R)$ and $G_R$ have been found. Moreover, we establish the relationship between the total domination number of $G_R$ and the number of prime ideals in $R$. Additionally, we identify all finite commutative rings with unity $R$ where the perfect domination number of $ℂ𝔸𝕐(R)$ is equal to $\left|R\right|$.

The star graph S_n, proposed by [1], has many advantages over the n-cube. It is shown in [2] that when a large number of vertices are deleted from S_n, the resulting graph can have at most two components, one of which is small. In this paper, we show that Cayley graphs generated by transpositions have this property.

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions.

We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic groups introduced by Kharlampovich, Khoussainov and Miasnikov and its extensions introduced by Elder and Taback. We obtain the upper and lower bounds for a length of an element of a wreath product in terms of the representations constructed.

We present a family of interconnection networks named the Cube-Of-Rings (COR) networks along with their basic graph-theoretic properties. Aspects of group graph theory are used to show the COR networks are symmetric and optimally fault tolerant. We present a closed-form expression of the diameter and optimal one-to-one routing algorithm for any member of the COR family. We also discuss the suitability of the COR networks as the interconnection network of scalable parallel computers.

This paper focuses on the formal proof of parallel programs dedicated to distributed memory symmetric interconnection networks; communications are realized by message passing. We have developed a method to formally verify the computational correctness of this kind of application. Using the notion of Cayley graphs to model the networks in the Nqthm theorem prover, we have formally specified and mechanically proven correct a large set of collective communication primitives. Our compositional approach allows us to reuse these libraries of pre-proven procedures to validate complex application programs within Nqthm. This is illustrated by three examples.

The star graph and the alternating group graph were introduced as competitive alternatives to the hypercube, and they are indeed superior over the hypercube under many measures. However, they do suffer from scaling issues. To address this, different generalizations, namely, the (n,k)-star graph and the arrangement graph were introduced to address this shortcoming. From another direction, the star graph was recognized as a special case of Cayley graphs whose generators can be associated with a tree. Nevertheless, all these networks appear to be very different and yet share many properties. In this paper, we will solve this mystery by providing a common generalization of all these networks. Moreover, we will show that these networks have strong connectivity properties.

We study some properties of the Cayley graph of R. Thompson's group F in generators x₀, x₁. We show that the density of this graph, that is, the least upper bound of the average vertex degree of its finite subgraphs is at least 3. It is known that a 2-generated group is not amenable if and only if the density of the corresponding Cayley graph is strictly less than 4. It is well known this is also equivalent to the existence of a doubling function on the Cayley graph. This means there exists a mapping from the set of vertices into itself such that for some constant K>0, each vertex moves by a distance at most K and each vertex has at least two preimages. We show that the density of the Cayley graph of a 2-generated group does not exceed 3 if and only if the group satisfies the above condition with K=1. Besides, we give a very easy formula to find the length (norm) of a given element of F in generators x₀, x₁. This simplifies the algorithm by Fordham. The length formula may be useful for finding the general growth function of F in generators x₀, x₁ and the growth rate of this function. In this paper, we show that the growth rate of F has a lower bound of .

By the density of a finite graph we mean its average vertex degree. For an $m$-generated group, the density of its Cayley graph in a given set of generators, is the supremum of densities taken over all its finite subgraphs. It is known that a group with $m$ generators is amenable if and only if the density of the corresponding Cayley graph equals $2m$.

A famous problem on the amenability of R. Thompson’s group $F$ is still open. Due to the result of Belk and Brown, it is known that the density of its Cayley graph in the standard set of group generators $\{x_0,x_1\}$, is at least $3.5$. This estimate has not been exceeded so far.

For the set of symmetric generators $S=\{x_1,{\bar{x}}_1\}$, where ${\bar{x}}_1=x_1{x}_0^{-1}$, the same example only gave an estimate of $3$. There was a conjecture that for this generating set equality holds. If so, $F$ would be non-amenable, and the symmetric generating set would have the doubling property. This would mean that for any finite set $X\subset F$, the inequality $\left|S^{\pm 1}X\right|\ge 2\left|X\right|$ holds.

In this paper, we disprove this conjecture showing that the density of the Cayley graph of $F$ in symmetric generators $S$ strictly exceeds $3$. Moreover, we show that even larger generating set $S_0=\{x_0,x_1,{\bar{x}}_1\}$ does not have doubling property.

In this paper, we introduce a concept of an evacuation scheme on the Cayley graph of an infinite finitely generated group. This is a collection of infinite simple paths bringing all vertices to infinity. We impose a restriction that every edge can be used a uniformly bounded number of times in this scheme. An easy observation shows that the existence of such a scheme is equivalent to non-amenability of the group. A special case happens if every edge can be used only once. These schemes are called pure. We obtain a criterion for the existence of such a scheme in terms of isoperimetric constant of the graph. We analyze R. Thompson’s group $F$, for which the amenability property is a famous open problem. We show that pure evacuation schemes do not exist for the set of generators $\{x_0,x_1,{\bar{x}}_1\}$, where ${\bar{x}}_1=x_1{x}_0^{-1}$. However, the question becomes open if edges with labels $x_0^{\pm 1}$ can be used twice. The existence of pure evacuation schemes for this version is implied by some natural conjectures.

We compute Cayley graphs and automorphism groups for all finite $n$-quandles of two-bridge and torus knots and links, as well as torus links with an axis.

To better understand the fundamental quandle of a knot or link, it can be useful to look at finite quotients of the quandle. One such quotient is the $n$-quandle (or, when $n=2$, the involutory quandle). Hoste and Shanahan [J. Hoste and P. D. Shanahan, Links with finite n-quandles, Algebraic Geom. Topol.17 (2017) 2807–2823.] gave a complete list of the links which have finite $n$-quandles; it remained to give explicit descriptions of these quandles. This has been done for several cases in [A. Crans, J. Hoste, B. Mellor and P. D. Shanahan, Finite n-qundles of torus and two-bridge links, J. Knot Theory Ramifications28 (2019) 1950028; J. Hoste and P. D. Shanahan, Involutory quandles of (2, 2, r)-Montesinos links, J. Knot Theory Ramifications26 (2017)]; in this work, we continue this project and explicitly describe the Cayley graphs for the finite involutory quandles of two-bridge links with an axis.

A novel and efficient neighbourhood broadcasting scheme is proposed for star interconnection networks, based on binomial trees and graph theoretic concepts. The optimal scheme has an upper bound of 1.33⌈log₂(n - 2)⌉ + O(1) time steps and it is applicable to both single-port and half-duplex modes of message passing communication.

Let Γ be a finite group with a nonempty subset A. The Cayley graphCay(Γ, A) of Γ generated by A is defined as the digraph with vertex set Γ and edge set {(x,y) | x^-1 y ∈ A}. Cay(Γ, A) can be regarded as an undirected graph if x^-1 ∈ A for all x ∈ A. Let denote the largest integer M so that there exists a set of integers A = {±1, ±a₂;…, ±a_k} such that the average distance between all pairs of vertices of Cay(ℤ_M,A) is at most r, where ℤ_M is the additive group of residue classes modulo M. It is proved in this paper that

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

The conditional diagnosability of interconnection networks has been studied in a number of ad-hoc methods resulting in various conditional diagnosability results. In this paper, we utilize these existing results to give an unified approach in studying this problem. Following this approach, we derive the exact value of the conditional diagnosability for a number of interconnection networks including Cayley graphs generated by 2-trees (which generalize alternating group graphs), arrangement graphs (which generalize star graphs and alternating group graphs), hyper Petersen networks, and dual-cube like networks (which generalize dual-cubes.)

Let $R$ be a finite commutative ring with nonzero identity and $U(R)$ be the set of all units of $R.$ The graph $\mathrm{\Gamma }$ is the simple undirected graph with vertex set $R$ in which two distinct vertices $x$ and $y$ are adjacent if and only if there exists a unit element $u$ in $U(R)$ such that $x+uy$ is a unit in $R.$ In this paper, we obtain degree of all vertices in $\mathrm{\Gamma }$ and in turn provide a necessary and sufficient condition for $\mathrm{\Gamma }$ to be Eulerian. Also, we give a necessary and sufficient condition for the complement $\overline{\mathrm{\Gamma }}$ to be Eulerian, Hamiltonian and planar.

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.

Let G be a p-group (p odd prime) and let X=Cay(G,S) be a 4-valent connected Cayley graph. It is shown that if G has nilpotent class 2, then the automorphism group Aut(X) of X is isomorphic to the semidirect product G_RAut(G, S), where G_R is the right regular representation of G and Aut(G, S) is the subgroup of the automorphism group Aut(G) of G which fixes S setwise. However the result is not true if G has nilpotent class 3 and this paper provides a couterexample.