Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cayley-graphs]

Questions concerning Cayley graphs, regardless of whether the group be finite, infinite, abelian, non-abelian. Strong connections to geometric group theory.

2
votes
0answers
52 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 ...
3
votes
1answer
81 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....
5
votes
1answer
232 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 ...
15
votes
1answer
279 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 ...
3
votes
2answers
109 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 ...
12
votes
1answer
275 views

Genus of Cayley graph of $A_5$ with two generators of order 5

The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. I am wondering what is its graph genus (orientable or non-orientable). The best I could get by trial and error is an ...
0
votes
2answers
99 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 ...
5
votes
1answer
109 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 ...
12
votes
0answers
175 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 ...
3
votes
0answers
260 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 ...
5
votes
0answers
233 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 ...
11
votes
4answers
933 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 ...
7
votes
2answers
1k views

Quasi-isometries vs Cayley Graphs

The following questions might be trivial, however, I couldn't solve them: Let $G$ be generated by a finite symmetric set $S$. Suppose that $\Gamma(G,S)$ is the corresponding right Cayley graph of $G$...
64
votes
6answers
6k 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 ...