Gromov (2003) 5 constructed finitely generated groups whose Cayley graphs contain all graphs from a given infinite sequence of expander graphs of unbounded girth and bounded diameter-to-girth ratio. ...These so-called Gromov monster groups provide examples of finitely generated groups that do not coarsely embed into Hilbert space, among other interesting properties. If graphs in Gromov's construction admit graphical small cancellation labellings, then one gets similar examples of Cayley graphs containing all the graphs of the family as isometric subgraphs. Osajda (2020) 11 recently showed how to obtain such labellings using the probabilistic method. In this short note, we simplify Osajda's approach, decreasing the number of generators of the resulting group significantly.
For a graph G=(V,E) and a set S⊆V(G) of size at least 2, a path in G is said to be an S-path if it connects all vertices of S. Two S-paths P1 and P2 are said to be internally disjoint if ...E(P1)∩E(P2)=0̸ and V(P1)∩V(P2)=S. Let πG(S) denote the maximum number of internally disjoint S-paths in G. The k-path-connectivityπk(G) of G is then defined as the minimum πG(S), where S ranges over all k-subsets of V(G). Cayley graphs often make good models for interconnection networks. In this paper, we consider the 3-path-connectivity of Cayley graphs generated by transposition trees Γn. We find that Γn always has a nice structure connecting any 3-subset S of V(Γn), according to the parity of n. Thereby, we show that π3Γn=⌊3n4⌋−1, for any n≥3.
We prove that any Cayley graph G with degree d polynomial growth does not satisfy {f(n)}-containment for any f=o(nd−2). This settles the asymptotic behaviour of the firefighter problem on such graphs ...as it was known that Cnd−2 firefighters are enough, answering and strengthening a conjecture of Develin and Hartke. We also prove that intermediate growth Cayley graphs do not satisfy polynomial containment, and give explicit lower bounds depending on the growth rate of the group. These bounds can be further improved when more geometric information is available, such as for Grigorchuk’s group.
Let S be a set of transpositions that generates the symmetric group Sn on n={1,2,…,n}, where n⩾3. The corresponding Cayley graph is denoted by Cay(Sn,S). The transposition generating graph T(S) of S ...is a graph with vertex set n and with vertices s and t being adjacent in T(S) whenever (st)∈S. A graph Γ is called induced matching extendable (shortly, IM-extendable) if every induced matching of Γ is included in a perfect matching of Γ. In this paper, we proved that Cay(Sn,S) is IM-extendable if and only if T(S) has true twins, where true twins are defined as a pair of vertices such that they have the same closed neighbourhood in T(S). In addition, we give a linear algorithm for checking true twins in T(S).
In this paper, we define meta-Cayley graphs on dihedral groups. We fully determine the automorphism groups of the constructed graphs in question. Further, we prove that some of the graphs that we ...have constructed do not admit subgroups which act regularly on their vertex set; thus proving that they cannot be represented as Cayley graphs on groups.
For S ⊆ G, let κ(S) denote the maximum number r of edge-disjoint trees T1,T2,…,Tr in G such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,⋯,r} and i ≠ j. For every 2 ≤ k ≤ n, the generalized k-connectivity of ...G κk(G) is defined as the minimum κ(S) over all k-subsets S of vertices, i.e., κk(G)= min {κ(S)|S⊆V(G)and|S|=k}. Clearly, κ2(G) corresponds to the traditional connectivity of G. The generalized k-connectivity can serve for measuring the capability of a network G to connect any k vertices in G. Cayley graphs have been used extensively to design interconnection networks. In this paper, we restrict our attention to two classes of Cayley graphs, the star graphs Sn and the bubble-sort graphs Bn, and investigate the generalized 3-connectivity of Sn and Bn. We show that κ3(Sn)=n−2 and κ3(Bn)=n−2.
Let G be a finite group with |G|≥4 and S be a subset of G. Given an automorphism σ of G, the twisted Cayley graph C(G,S)σ is the graph with G as its set of vertices, and the neighbourhood of a vertex ...is obtained by applying σ to its neighbourhood in the Cayley graph of G with respect to S. If C(G,S)σ is undirected and connected, then we prove that the nontrivial spectrum of its normalised adjacency operator is bounded away from −1 and this bound depends only on its degree, the order of σ and the vertex Cheeger constant of C(G,S)σ. The twisted Cayley sum graph CΣ(G,S)σ is defined similarly and we establish an analogous result for it. Further, we prove an analogous result for the Schreier graphs satisfying certain conditions.
We construct a 2-generated group $\Gamma $ such that its Cayley graph possesses finite connected subsets with arbitrarily large finite Heesch number. Thus we obtain an example of a Cayley graph with ...an infinite Heesch number.
PDF
