2018/08/28 by Hujdurovic, Ademir
#05C25 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.09534
A clique (resp., independent set) in a graph is strong if it intersects every maximal independent sets (resp., every maximal cliques). A graph is CIS if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique C in a vertex-transitive graph Γ is strong if and only if |C||I|=|V(Γ)| for every maximal independent set I of Γ. Based on this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.