Akademska digitalna zbirka SLovenije - logo
E-resources
Peer reviewed Open access
  • Strong cliques in vertex‐tr...
    Hujdurović, Ademir

    Journal of graph theory, December 2020, 2020-12-00, 20201201, Volume: 95, Issue: 4
    Journal Article

    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 C in a vertex‐transitive graph Γ is strong if and only if ∣ C ∣ ∣ I ∣ = ∣ V ( Γ ) ∣ for every maximal independent set I 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.