All Questions
Tagged with cayley-graphs graph-theory
41
questions
76
votes
6
answers
9k
views
Which graphs are Cayley graphs?
Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...
- 220k
26
votes
4
answers
2k
views
What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?
It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0,...
- 13.7k
18
votes
7
answers
3k
views
Spectral properties of Cayley graphs
Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good ...
- 3,271
16
votes
1
answer
507
views
Chromatic numbers of infinite abelian Cayley graphs
The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
- 19.1k
16
votes
0
answers
311
views
Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?
My question is
Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must
$G$ have the following substructures?
i) a leafless spanning
tree;
ii) a spanning forest consisting ...
- 1,844
15
votes
0
answers
238
views
Approximation of the effective resistance on Cayley graph
Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...
- 385
12
votes
2
answers
713
views
Is the Petersen graph a "Cayley graph" of some more general group-like structure?
The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?
- 1,803
11
votes
4
answers
1k
views
Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?
It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.
In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...
- 111
5
votes
1
answer
312
views
$C_4\times C_2 : C_2$: what does this mean?
I am reading this paper where the object $C_4\times C_2 : C_2$ is used as a group structure. I know that $C_n$ is a cyclic group but don't know what kind of operation between groups is identified by ...
- 219
5
votes
2
answers
751
views
A generously vertex transitive graph which is not Cayley?
A graph is vertex transitive if $x \mapsto y$ by an automorphism.
A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
GVT $\rightarrow$ unimodular. ...
- 153
5
votes
1
answer
374
views
Cayley graph properties
Consider an infinite graph that satisfies the following property: if any finite set of vertices is removed (and all the adjacent edges), then the resulting graph has only one infinite connected ...
5
votes
1
answer
139
views
Inertia of a class of Cayley graphs
Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of ...
- 421
5
votes
0
answers
189
views
Groups of non-orientable genus 1 and 2
The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
- 150
5
votes
0
answers
155
views
When is a Schreier coset graph vertex transitive
When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...
- 1,841
5
votes
0
answers
277
views
Complexity of property of being vertex-transitive resp. of being a Cayley graph
Suppose I gave you a finite graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you a vertex transitive finite graph, and ...
- 95.3k
4
votes
2
answers
416
views
Transposition Cayley graphs are planar
Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...
- 1,841
4
votes
1
answer
249
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 225
4
votes
1
answer
166
views
Cliques in Cayley graph on $n$-cycles
Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....
- 173
4
votes
1
answer
226
views
Total coloring conjecture for Cayley graphs
The total coloring conjecture (TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
- 1,841
3
votes
1
answer
95
views
Edge coloring of a graph on alternating groups
Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...
- 1,841
3
votes
0
answers
63
views
Hamiltonian cycles in Cayley graph on alternating group
Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=...
- 1,841
3
votes
0
answers
289
views
Induced graphs of Cayley graph
I have a Cayley graph $\mathrm{Cay}(G,S)$, its group presentation $G=\langle S | R \rangle$, and it becomes a metric graph by assigning a length equal to $1$ to each edge. I also have an induced ...
- 31
2
votes
2
answers
235
views
Distance regular Cayley graphs on $Z_2^n$?
Let $Z_2^n$ be group $Z_2 \times Z_2 \times \cdots \times Z_2$ with operation Exclusive-or. I'd like to know if the $Cay(Z_2^n,S)$ for $S \subset Z_2^n \setminus \{0\}$ is distance regular graph or ...
- 29
2
votes
1
answer
90
views
Imposing reciprocity in the definition of vertex-transitivity
A simple, undirected graph is vertex-transitive if for any pair of vertices $x,y$, there exists an automorphism (adjacency-preserving self-bijection) $\phi$ such that $\phi(x)=y$.
What if, instead of ...
- 170
2
votes
0
answers
132
views
Chromatic numbers of Cayley graphs induced by Hamming balls
The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': ...
- 794
2
votes
0
answers
59
views
Path-covering for vertex-transitive graphs
I have the following dummy problem:
Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...
- 2,874
1
vote
1
answer
158
views
Cayley graphs on $Z_{11}$ and $Z_p$
I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...
- 219
1
vote
2
answers
121
views
Difference in chromatic number between Schreier coset graphs and Cayley graphs
Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the ...
- 1,841
1
vote
1
answer
221
views
Cayley graphs do not have isolated maximal cliques
Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...
- 1,841
1
vote
0
answers
46
views
Circulant graphs chromatically dominated by powers of cycles
Suppose we can color the vertices of powers of cycles $C_n^k$ using $c$ colors such that each of the color classes $c_i$ have $v_i$ number of vertices. Can we always color the circulant of degree $2k$ ...
- 1,841
1
vote
0
answers
117
views
halved and folded hypercube duality
Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\...
- 201
1
vote
0
answers
110
views
Chromatic number of certain graphs with high maximum degree
Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...
- 1,841
1
vote
0
answers
150
views
Are all even regular undirected Cayley graphs of Class 1?
Are even order Cayley graphs of Class 1, that is, can they be edge-colored with exactly $m$ colors, where $m$ is the degree of each vertex?
I think yes, because of the symmetry the Cayley graphs ...
- 1,841
0
votes
2
answers
134
views
coloring infinite vertex transitive graph without large cliques
Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...
- 11.2k
0
votes
1
answer
110
views
Bound on chromatic number of graphs on any finite $p$-group
Is the chromatic number of a Cayley graph on $p$-groups with any generating set bounded by the chromatic number of the maximal induced circulant subgraph?
I think yes. Because for one, the main ...
- 1,841
0
votes
1
answer
78
views
Extending the vertex coloring of circulant graph to graph on $p$-group
Let $G_1$ be a circulant graph of prime order $p$. This implies that $G_1$ is the Cayley graph on $\mathbb{Z}_p$ with some generating set $S_1$. I am interested in knowing the characterizations of the ...
- 1,841
0
votes
1
answer
332
views
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...
- 1,841
0
votes
0
answers
112
views
Procedure to color the edges of a circulant graph
From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
- 1,841
0
votes
1
answer
111
views
Recognizing perfect Cayley graphs as tensor products
It is known (and can easily be seen) that a unitary Cayley graph on $n=\prod_ip_i$, ($p_i$ distinct primes) vertices with $n$ square-free can be recognized as the tensor product of the graphs $K_{p_i}$...
- 1,841
-1
votes
1
answer
168
views
Which line graphs of Cayley graphs are Cayley
When are the line graphs of Cayley graphs Cayley?
From this link we can know when the line graphs of complete graphs are cayley. But, my question pertains to the larger class of Cayley graphs. Are ...
- 1,841
-1
votes
1
answer
195
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
- 1,841