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 half the order of $G$, then is it possible for some group $H$ that $G$ has a unique "disjoint maximal clique". By "disjoint maximal clique", I mean a clique equal to the clique size of the graph, and such that any other clique of same order would not be vertex disjoint with the prior clique.

I don't think so. For, if $(e),(s_1),(s_1\cdot s_2),(s_1\cdot s_2\cdot s_3),\ldots,(s_1\cdot s_2\cdots s_n)$ be the sequence of vertices in a maximal clique, then I think even $(s_1^2),(s_1^3),(s_1^2\cdot s_2),\ldots,(s_1^2\cdot s_2\cdots s_n)$ would also be a sequence of vertices in a maximal clique, where $e$ denotes the identity element. But, what if $s_1$ is an order $2$ or $3$ element. How do we ensure that there always exist a disjoint clique apart from the clique $(e),(s_1),(s_1\cdot s_2),(s_1\cdot s_2\cdot s_3),\ldots,(s_1\cdot s_2\cdots s_n)$? Will this be true at least for the case when $H$ is an abelian/cyclic group? Any hints? Thanks beforehand.

  • $\begingroup$ Your question is not clear. "Disjoint" is a property of two things, not a property of one thing. $\endgroup$ May 23, 2020 at 9:04
  • $\begingroup$ @BrendanMcKay edited the post. $\endgroup$
    – vidyarthi
    May 23, 2020 at 11:17
  • $\begingroup$ Your terminology looks confusing. "Unique maximal clique" usually means that it is a maximal clique and there is no other maximal clique. $\endgroup$ May 23, 2020 at 11:23
  • $\begingroup$ @FedorPetrov no, my meaning is that there is a maximal clique and no other "vertex disjoint" maximal clique $\endgroup$
    – vidyarthi
    May 23, 2020 at 11:41
  • 2
    $\begingroup$ Rephrased: "Do all maximal cliques in $G$ pairwise intersect"? (Also I don't see why you need to assume $G$ is non-complete: then your condition is trivially satisfied.) $\endgroup$ May 23, 2020 at 12:44

1 Answer 1


Let $G$ be the linegraph of the complete graph $K_n$ for $n\geq 5$. For some but not all $n$, $G$ is a Cayley graph, see Chris Godsil's answer to another question.

$G$ has $\binom n2$ vertices and degree $2n-4$. The maximum cliques of $G$ correspond to the edges incident with one vertex and so they have size $n-1$. Moreover, the cliques corresponding to two different vertices of $K_n$ have one point in common, namely the edge between those two vertices.

Therefore, $G$ is an example of a Cayley graph for which any two maximum cliques intersect, even though the maximum cliques only have size about the square root of the number of vertices.

I wonder if this example is optimal in some sense.

ADDED: Here is an exposition of Ilya's argument from the comments.

Theorem. If a vertex-transitive graph with $N$ vertices has cliques of size $k$ such that $k^2<N$, then there are two such cliques which are disjoint.

Proof. Take a fixed $k$-clique $C$ and apply a random automorphism $\gamma$. The expected number of elements of $C$ that map to an element of $C$ is $k^2/N$, so $k^2<N$ implies that $C$ must sometimes map to a clique disjoint from itself.

In the case of a Cayley graph of a group $\varGamma$, we can use a random non-identity element of $\varGamma$ to improve the inequality to $k(k-1)<N-1$.

There is a clique size gap of about $\sqrt 2$ between these bounds and the linegraph of a complete graph. So the problem is still missing a complete solution.

  • 2
    $\begingroup$ It is optimal in some sense: if a Cayley graph contains a clique of size $<\sqrt n$, then it contains its isomorphic copy, from probabilistic reasons $\endgroup$ May 23, 2020 at 16:01
  • $\begingroup$ @IlyaBogdanov you mean if a cayley graph has clique size $< \sqrt n$, then it has disjoint cliques of maximal size? Any reference for this? $\endgroup$
    – vidyarthi
    May 23, 2020 at 16:51
  • 1
    $\begingroup$ If a clique size is $k$, there are $n$ copies of one clique (starting from any vertex), and only $k(k-1)+1$ of them intersects the initial one (any vertex of a copy may coincide with any vertex of the origin). $\endgroup$ May 23, 2020 at 16:54
  • $\begingroup$ will the property hold for cayley graphs on cyclic or abelian groups at least? $\endgroup$
    – vidyarthi
    May 23, 2020 at 16:56
  • $\begingroup$ @IlyaBogdanov in saying that there are $n$ cliques of size $k$, you are using the vertex transitivity of the graph, isnt it? So this should hold for vertex transitive graphs also, right? $\endgroup$
    – vidyarthi
    May 23, 2020 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.