Narrow Results

Let $\mathrm{\text{Γ}}=(V(\mathrm{\text{Γ}}),E(\mathrm{\text{Γ}}))$ be a graph. A subset $C$ of $V(\mathrm{\text{Γ}})$ is called a perfect code of $\mathrm{\text{Γ}}$, when $C$ is an independent set and every vertex of $V(\mathrm{\text{Γ}})\setminus C$ is adjacent to exactly one vertex in $C$. Let $\mathrm{\text{Γ}}$ = Cay(G, S) be a Cayley graph of a finite group $G$. A subset $C$ of $G$ is called a perfect code of $G$, when there exists a Cayley graph $\mathrm{\text{Γ}}$ of $G$ such that $C$ is a perfect code of $\mathrm{\text{Γ}}$. Recently, groups whose set of all subgroup perfect codes forms a chain are classified. Also, groups with no proper nontrivial subgroup perfect code are characterized. In this paper, we generalize it and classify groups whose set of all non-perfect code subgroups forms a chain.

Let $s$ be a positive integer. A graph is $s$-transitive if its automorphism group is transitive on s-arcs but not on $(s+1)$-arcs. In this paper, we study all tetravalent $s$-transitive graphs of order $6p^2$.

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important metric for fault tolerance of interconnection networks. A graph $G$ is said to be maximally local-connected if each pair of vertices $u$ and $v$ are connected by $min\{d_G(u),d_G(v)\}$ vertex-disjoint paths. In this paper, we show that Cayley graphs generated by $m$($\ge 7$) transpositions are $(m-2)$-fault-tolerant maximally local-connected and are also $(m-3)$-fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have a triangle, $(m-2)$-fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have no triangles. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, Cayley graphs generated by $m$($\ge 7$) transpositions are $(m-1)$-fault-tolerant maximally local-connected if their corresponding transposition generating graphs have no triangles.

The Cayley graph generated by a transposition tree ${\mathrm{\Gamma }}_n$ is a class of Cayley graphs that contains the star graph and the bubble sort graph. A graph $G$ is called strongly Menger (SM for short) (edge) connected if each pair of vertices $x,y$ are connected by $min\{d_G(x),d_G(y)\}$ (edge)-disjoint paths, where $d_G(x),d_G(y)$ are the degree of $x$ and $y$ respectively. In this paper, the maximally edge-fault-tolerant and the maximally vertex-fault-tolerant of ${\mathrm{\Gamma }}_n$ with respect to the SM-property are found and thus generalize or improve the results in [19, 20, 22, 26] on this topic.

Let be a nonempty class of finite groups closed under taking subgroups, quotients and extensions. We consider groups G endowed with their pro- topology, and say that G is 2-subgroup separable if whenever H and K are finitely generated closed subgroups of G, then the subset HK is closed. We prove that if the groups G₁ and G₂ are 2-subgroup separable, then so is their free product G₁*G₂. This extends a result to T. Coulbois. The proof uses actions of groups on abstract and profinite trees.

We first introduce a loop shortening property for metric spaces, generalizing the property considered by M. Elder on Cayley graphs of finitely generated groups. Then using this metric property, we define a very broad loop shortening property for finitely generated groups. Our definition includes Elder's groups, and unlike his definition, our property is obviously a quasi-isometry invariant of the group. Furthermore, all finitely generated groups satisfying this general loop shortening property are also finitely presented and satisfy a quadratic isoperimetric inequality. Every CAT(0) cubical group is shown to have this general loop shortening property.

Let S be a finite semigroup. In this paper, we introduce the functions φ_s:S* → S*, first defined by Rhodes, given by φ_s([a₁,a₂,…,a_n]) = [sa₁,sa₁a₂,…,sa₁a₂ ⋯ a_n]. We show that if S is a finite aperiodic semigroup, then the semigroup generated by the functions {φ_s}_{s ∈ S} is finite and aperiodic.

We introduce a property of geodesic metric spaces, called the road trip property, that generalizes hyperbolic and convex metric spaces. This property is shown to be invariant under quasi-isometry. Thus, it leads to a geometric property of finitely generated groups, also called the road trip property. The main result is that groups with the road trip property are finitely presented and satisfy a quadratic isoperimetric inequality. Examples of groups with the road trip property include hyperbolic, semihyperbolic, automatic and CAT(0) groups.

An infinite graph Γ is minor excluded if there is a finite graph that is not a minor of Γ. We prove that minor excluded graphs have finite Assouad–Nagata dimension and study minor exclusion for Cayley graphs of finitely generated groups. Our main results and observations are: (1) minor exclusion is not a group property: it depends on the choice of generating set; (2) a group with one end has a generating set for which the Cayley graph is not minor excluded; (3) there are groups that are not minor excluded for any set of generators, like ℤ³; (4) minor exclusion is preserved under free products; and (5) virtually free groups are minor excluded for any choice of finite generating set.

The diagnosis of faulty processors plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Zheng et al. showed that the diagnosability of the n-dimensional star graph S_n is n - 1. Lai et al. introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation when no faulty set can contain all the neighbors of any vertex in the system. In this paper, we study the conditional diagnosability of Cayley graphs generated by transposition trees (which include the star graphs) under the comparison model, and show that it is 3n - 8 for n ≥ 4, except for the n-dimensional star graph, for which it is 3n - 7. Hence the conditional diagnosability of these graphs is about three times larger than their classical diagnosability.

Because of its applications in network theory, the wide diameter of graphs has been studied extensively in recent years. It is still an open problem to compute the wide diameter of Cayley graphs. This paper investigates the wide diameter of Cayley graphs of ℤ_m, the cyclic group of residue classes modulo m. It is proved that the k-wide diameter of the Cayley graph Cay(Z_m, A) generated by a k-element set A is d + 1 for k = 2 and ≤ d + 1 for k = 3, where d is the diameter of Cay(ℤ_m, A).

We introduce cube-connected circulants as efficient models for communication networks. We give an algorithm for computing a shortest path between any pair of vertices in a cube-connected circulant. We give formulas for the diameter of a cube-connected circulant and the distance between any pair of vertices in such a graph. Then we give an embedding of cube-connected circulants into hypercubes, and an embedding of hypercubes into cube-connected circulants. We show cube-connected circulants outperform a few well-known network structures in several invariants.

The largest order $C(d,k)$ of a Cayley graph of degree $d\ge 3$ and diameter $k\ge 2$ cannot exceed the Moore bound $M(d,k)$ the asymptotic form of which is $M(d,k)=d^k-O(d^{k-1})$ for $d\to \infty$ and a fixed k. The second and the third author and the three authors proved by direct constructions that the Moore bound for diameter $k=2$ and $k=3$, respectively, can be approached asymptotically by Cayley graphs in the sense that $C(d,k)/M(d,k)\to 1$ for some sequences of degrees $d\to \infty$. In this note we present a unifying principle underlying the two results, based on the existence of certain regular orbits of automorphism groups of suitable graphs.

In the degree-diameter problem for Abelian Cayley and circulant graphs of diameter 2 and arbitrary degree d there is a wide gap between the best lower and upper bounds valid for all d, being quadratic functions with leading coefficient 1/4 and 1/2 respectively. Recent papers have presented constructions which increase the coefficient of the lower bound to be at or just below 3/8 for sparse sets of degree d related to primes of specific congruence classes. The constructions use the direct product of the multiplicative and additive subgroups of a Galois field and a specific cyclic group of coprime order. It was anticipated that this approach would be capable of yielding further improvement towards the upper bound value of 1/2. In this paper, however, it is proved that the quadratic coefficient of the order of families of Abelian Cayley graphs of this class of construction can never exceed the value of 3/8, establishing an asymptotic limit of 3/8 for the quadratic coefficient of families of extremal graphs of this class.

By applying recent results from number theory these constructions can be extended to be valid for every degree above some threshold, establishing an improved asymptotic lower bound approaching 3/8 for general Abelian Cayley and circulant graphs of diameter 2 and arbitrary degree d.

As a variant of $Q_n$, Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484–490] introduced the balanced hypercube $B{H}_n$ as an interconnection network topology for computing systems. In this paper, we show that $B{H}_n$ is a lexicographic product of two graphs, and using this, we show that every minimum cyclic vertex-cut of $B{H}_n$ isolates a 4-cycle, and prove that the edge neighbor connectivity of $B{H}_n$ is $2n$.

In this paper, we introduce the Cayley graph of a partially ordered set (poset). Let (P, ≤) be a poset, and let S be a subset of P. We define the undirected Cayley graph of P, denoted by Cay(P, S), as a graph with vertex-set P and edge-set E consisting of those sets {x, y} such that y ∈ {x, s}^ℓ or x ∈ {y, s}^ℓ for some s ∈ S, where for a subset T of P, T^ℓ is the set of all x ∈ P such that x ≤ t, for all t ∈ T. We study some basic properties of Cay(P, S) such as connectivity, diameter and girth.

In this paper, we introduce and study a new class of Cayley graphs.

For any positive integer $k$, let ${{𝒢}}_k$ denote the set of finite groups $G$ such that all Cayley graphs $\mathrm{\text{Cay}}(G,S)$ are integral whenever $\left|S\right|\le k$. Estélyi and Kovács [On groups all of whose undirected Cayley graphs of bounded valency are integral, Electron. J. Combin.21 (2014) #P4.45.] classified ${{𝒢}}_k$ for each $k\ge 4$. In this paper, we characterize the finite groups each of whose cubic Cayley graphs is integral. Moreover, the class ${{𝒢}}_3$ is characterized. As an application, the classification of ${{𝒢}}_k$ is obtained again, where $k\ge 4$.

The adjacency spectrum $\mathrm{\text{Spec}}(\mathrm{\Gamma })$ of a graph $\mathrm{\Gamma }$ is the multiset of eigenvalues of its adjacency matrix. Two graphs with the same spectrum are called cospectral. A graph $\mathrm{\Gamma }$ is “determined by its spectrum” (DS for short) if every graph cospectral to it is in fact isomorphic to it. A group is DS if all of its Cayley graphs are DS. A group $G$ is Cay-DS if every two cospectral Cayley graphs of $G$ are isomorphic. In this paper, we study finite DS groups and finite Cay-DS groups. In particular we prove that a finite DS group is solvable, and every non-cyclic Sylow subgroup of a finite DS group is of order $4$, $8$, $16$ or $9$. We also give several infinite families of non-Cay-DS solvable groups. In particular we prove that there exist two cospectral non-isomorphic $6$-regular Cayley graphs on the dihedral group of order $2p$ for any prime $p\ge 13$.

A Cayley graph $\mathrm{\Gamma }=Cay(G,S)$ is said to be core-free if $G$ is core-free in some $X$ for $G\le X\le Aut\mathrm{\Gamma }$. A graph $\mathrm{\Gamma }$ is called $s$-regular if $Aut\mathrm{\Gamma }$ acts regularly on its $s$-arcs. It is shown in this paper that if $s\le 2$, then there exist no core-free tetravalent $s$-regular Cayley graphs; and for $s\ge 3$, every tetravalent $s$-regular Cayley graph is a normal cover of one of the three known core-free graphs. In particular, a characterization of tetravalent $s$-regular Cayley graphs is given.