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.
A connected graph of order at least 2k+2 is k-extendable for a non-negative integer k if it contains a perfect matching and every matching of size k can be extended to a perfect matching. The ...extendability number of the graph is the maximum k such that the graph is k-extendable. In this paper, we prove that, for a Cayley graph Γ of a symmetric group with respect to a generating set of size m consisting of transpositions, the extendability number of Γ is m−1.
We show that the Waring number over a finite field Fq, denoted as g(k,q), when exists coincides with the diameter of the generalized Paley graph Γ(k,q)=Cay(Fq,Rk) with Rk={xk:x∈Fq∗}. We find infinite ...new families of exact values of g(k,q) from a characterization of graphs Γ(k,q) which are also Hamming graphs proved by Lim and Praeger in 2009. Then, we show that every positive integer is the Waring number for some pair (k,q) with q not a prime. Finally, we find a lower bound for g(k,p) with p prime by using that Γ(k,p) is a circulant graph in this case.
A Cayley graph is said to be an NNN-graph if its automorphism group contains two isomorphic regular subgroups where one is normal and the other is non-normal. In this paper, we show that there exist ...NNN-graphs among the Cayley graphs for symmetric groups Sn if and only if n⩾5.
High-Rate Storage Codes on Triangle-Free Graphs Barg, Alexander; Zemor, Gilles
IEEE transactions on information theory,
2022-Dec., 2022-12-00, 2022-12, Volume:
68, Issue:
12
Journal Article
Peer reviewed
Open access
Consider an assignment of bits to the vertices of a connected graph <inline-formula> <tex-math notation="LaTeX">G(V,E) </tex-math></inline-formula> with the property that the value of each vertex is ...a function of the values of its neighbors. A collection of such assignments is called a storage code of length <inline-formula> <tex-math notation="LaTeX">|V| </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. If <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate <inline-formula> <tex-math notation="LaTeX">> 1/2 </tex-math></inline-formula> is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems.
Let S be a subset of finite cyclic group Zn not containing the identity element 0 with S=−S. Cayley graphs on Zn with respect to S are called circulant graphs and denoted by Cay(Zn,S). In this paper, ...for connected non-complete circulant graphs Cay(Zn,S) of degree |S|=p−1 with p prime, we give a necessary and sufficient condition for the existence of efficient dominating sets, and characterize all efficient dominating sets if exist. We also obtain similar results for Cay(Zn,S) of degree |S|=pq−1 and pm−1, where p,q are primes, m is a positive integer, and |S|+1 is relatively prime to n|S|+1. Moreover, we give a necessary and sufficient condition for the existence of efficient dominating sets in Cay(Zn,S) of order n=pkq,p2q2,pqr,p2qr,pqrs and degree |S|, where p,q,r,s are distinct primes, k is a positive integer, and |S|+1 is relatively prime to n|S|+1.
For a finite group G and an inverse closed subset S⊆G∖{e}, the Cayley graph X(G,S) has vertex set G and two vertices x,y∈G are adjacent if and only if xy−1∈S. Two graphs are called cospectral if ...their adjacency matrices have the same spectrum. Let p≥3 be a prime number and T4p be the dicyclic group of order 4p. In this paper, with the help of the characters from representation theory, we construct a large family of pairwise non-isomorphic and cospectral Cayley graphs over the dicyclic group T4p with p≥23, and find several pairs of non-isomorphic and cospectral Cayley graphs for 5≤p≤19.
We consider generalized Paley graphs
$ \Gamma (k,q) $
Γ
(
k
,
q
)
, generalized Paley sum graphs
$ \Gamma ^+(k,q) $
Γ
+
(
k
,
q
)
, and their corresponding complements
$ \bar \Gamma (k,q) $
Γ
¯
(
k
,
...q
)
and
$ \bar \Gamma ^+(k,q) $
Γ
¯
+
(
k
,
q
)
, for k = 3, 4. Denote by
$ \Gamma =\Gamma ^*(k,q) $
Γ
=
Γ
∗
(
k
,
q
)
either
$ \Gamma (k,q) $
Γ
(
k
,
q
)
or
$ \Gamma ^+(k,q) $
Γ
+
(
k
,
q
)
. We compute the spectra of
$ \Gamma (3,q) $
Γ
(
3
,
q
)
and
$ \Gamma (4,q) $
Γ
(
4
,
q
)
and from them we obtain the spectra of
$ \Gamma ^+(3,q) $
Γ
+
(
3
,
q
)
and
$ \Gamma ^+(4,q) $
Γ
+
(
4
,
q
)
also. Then we show that, in the non-semiprimitive case, the spectrum of
$ \Gamma (3,p^{3\ell }) $
Γ
(
3
,
p
3
ℓ
)
and
$ \Gamma (4,p^{4\ell }) $
Γ
(
4
,
p
4
ℓ
)
with p prime can be recursively obtained, under certain arithmetic conditions, from the spectrum of the graphs
$ \Gamma (3,p) $
Γ
(
3
,
p
)
and
$ \Gamma (4,p) $
Γ
(
4
,
p
)
for any
$ \ell \in \mathbb{N} $
ℓ
∈
N
, respectively. Using the spectra of these graphs we give necessary and sufficient conditions on the spectrum of
$ \Gamma ^*(k,q) $
Γ
∗
(
k
,
q
)
such that
$ \Gamma ^*(k,q) $
Γ
∗
(
k
,
q
)
and
$ \bar \Gamma ^*(k,q) $
Γ
¯
∗
(
k
,
q
)
are equienergetic for k = 3, 4. In a previous work we have classified all bipartite regular graphs
$ \Gamma _{\rm bip} $
Γ
bip
and all strongly regular graphs
$ \Gamma _{\rm srg} $
Γ
srg
which are complementary equienergetic, i.e.
$ \{\Gamma _{\rm bip}, \bar {\Gamma }_{\rm bip}\} $
{
Γ
bip
,
Γ
¯
bip
}
and
$ \{\Gamma _{\rm srg}, \bar {\Gamma }_{\rm srg}\} $
{
Γ
srg
,
Γ
¯
srg
}
are equienergetic pairs of graphs. Here we construct infinite pairs of equienergetic non-isospectral regular graphs
$ \{\Gamma, \bar \Gamma \} $
{
Γ
,
Γ
¯
}
which are neither bipartite nor strongly regular.
We study the normal Cayley graphs Cay(Sn,C(n,I)) on the symmetric group Sn, where I⊆{2,3,…,n} and C(n,I) is the set of all cycles in Sn with length in I. We prove that the strictly second largest ...eigenvalue of Cay(Sn,C(n,I)) can only be achieved by at most four irreducible representations of Sn, and we determine further the multiplicity of this eigenvalue in several special cases. As a corollary, in the case when I contains neither n−1 nor n we know exactly when Cay(Sn,C(n,I)) has the Aldous property, namely the strictly second largest eigenvalue is attained by the standard representation of Sn, and we obtain that Cay(Sn,C(n,I)) does not have the Aldous property whenever n∈I. As another corollary of our main results, we prove a recent conjecture on the second largest eigenvalue of Cay(Sn,C(n,{k})) where 2≤k≤n−2.
PDF
