0
$\begingroup$

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$. Then, would $G$ have $\frac{n}{\omega}$ disjoint maximal cliques, that is $\frac{n}{\omega}$ maximal cliques of order $\omega$ which are mutually vertex disjoint.

The result is immediate if $G$ is complete multipartite, or even if $G$ is a unitary cayley graph. From here, we know that, if $\omega|n$, $G$ would be CIS(clique intersection stable), that is every maximal clique intersects every maximal independent set. I guess it should work in this case, and also for other graphs on abelian groups. Will the result hold even for Cayley graphs of non-abelian groups? Thanks beforehand.

$\endgroup$
0
$\begingroup$

This would work for any perfect Cayley graph. Since we have $n$ vertices and the clique number is $\omega$, we have $n$ different $\omega$-cliques (of course several intersecting). Hence, any maximal independent set would contain $\frac{n}{\omega}$ vertices in it. In fact, the vertices would be distributed equitably in $\omega$ independent sets in a $\omega$ coloring. By the paper linked in the question, we have that every maximal clique intersects every maximal independent set. Therefore each disjoint maximal independent set of vertices has one vertex of each maximal clique. Thus, there are $\frac{n}{\omega}$ vertex disjoint maximal cliques.

| cite | improve this answer | |
$\endgroup$

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.