Strong cliques in vertex-transitive graphs |
| |
Authors: | Ademir Hujdurovi? |
| |
Institution: | University of Primorska, Andrej Maru?i? Institute, Koper, Slovenia |
| |
Abstract: | A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (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 in a vertex-transitive graph is strong if and only if for every maximal independent set of . On the basis of 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. |
| |
Keywords: | CIS graph localizable graph maximum clique strong clique vertex-transitive graph |
|
|