Strong cliques in vertex‐transitive graphs

DOI10.1002/JGT.22573MaRDI QIDQ6134644zbMATH OpenOpenAlexFDO

Authors Ademir Hujdurović

Publication date 22 August 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.09534

zbMATH Keywords

maximum cliquestrong cliquevertex-transitive graphCIS graphlocalizable graph

Mathematics Subject Classification ID

Graph theory (05Cxx)

Abstract: 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 $Gamma$ is strong if and only if $|C||I|=|V(Gamma)|$ for every maximal independent set $I$ of $Gamma$. 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.

Recommendations

• Strong cliques in diamond-free graphs
• Strong cliques in diamond-free graphs
• Strong cliques in claw-free graphs
• Graphs vertex-partitionable into strong cliques
• Strong cliques and equistability of EPT graphs
• Strong cliques and stable sets
• Clique graph characterizations of strongly chordal graphs
• Strong cliques and forbidden cycles
• scientific article; zbMATH DE number 19181
• On cliques in graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3889583 (Why is no real title available?)
• scientific article; zbMATH DE number 3910420 (Why is no real title available?)
• scientific article; zbMATH DE number 1286748 (Why is no real title available?)
• A characterization of almost CIS graphs
• A note on coloring vertex-transitive graphs
• Detecting strong cliques
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Graphs vertex-partitionable into strong cliques
• Hardness of computing clique number and chromatic number for Cayley graphs
• Modeling \(k\)-coteries by well-covered graphs
• On CIS circulants
• On a conjecture of Meyniel
• On equistable, split, CIS, and related classes of graphs
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• On split and almost CIS-graphs
• On the perfect graph conjecture
• Stochastic graphs and strongly perfect graphs - a survey
• Uniquely colorable Cayley graphs
• Vertex-transitive CIS graphs
• WELL-COVERED GRAPHS: A SURVEY

Cited in

(2)

• Strong cliques and equistability of EPT graphs
• Graphs vertex-partitionable into strong cliques

This page was built for publication: Strong cliques in vertex‐transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134644)