Vertex-transitive CIS graphs

DOI10.1016/J.EJC.2014.09.007MaRDI QIDQ472401zbMATH OpenOpenAlexFDO

Authors Edward Dobson, Ademir Hujdurović, Martin Milanič, Gabriel Verret

Publication date 19 November 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphwell-covered graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. A graph is well-covered if all its maximal stable sets are of the same size, co-well-covered if its complement is well-covered, and vertex-transitive if, for every pair of vertices, there exists an automorphism of the graph mapping one to the other. We show that a vertex-transitive graph is CIS if and only if it is well-covered, co-well-covered, and the product of its clique and stability numbers equals its order. A graph is irreducible if no two distinct vertices have the same neighborhood. We classify irreducible well-covered CIS graphs with clique number at most 3 and vertex-transitive CIS graphs of valency at most 7, which include an infinite family. We also exhibit an infinite family of vertex-transitive CIS graphs which are not Cayley.

Recommendations

• On CIS circulants
• On graphs whose maximal cliques and stable sets intersect
• The GI-properties of the vertex-transitive graphs of simple groups
• On isomorphisms of vertex-transitive graphs
• scientific article; zbMATH DE number 773194

Cites work

• scientific article; zbMATH DE number 5914964 (Why is no real title available?)
• scientific article; zbMATH DE number 558656 (Why is no real title available?)
• A characterization of a class of symmetric graphs of twice prime valency
• A characterization of almost CIS graphs
• A characterization of perfect graphs
• A class of weakly perfect graphs
• A note on coloring vertex-transitive graphs
• Algorithmic graph theory and perfect graphs
• Bipartite bihypergraphs: a survey and new results
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Graphs of linear clique-width at most 3
• Maximal chains and antichains
• On CIS circulants
• On a Class of Fixed-Point-Free Graphs
• On graphs whose maximal cliques and stable sets intersect
• On split and almost CIS-graphs
• On the maximum independent set problem in subclasses of planar graphs
• On well-covered triangulations. II.
• On well-covered triangulations. III
• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs
• Randomly matchable graphs
• Some covering concepts in graphs
• The strong perfect graph theorem
• The structure of well-covered graphs with no cycles of length 4
• The transitive groups of degree twelve
• WELL-COVERED GRAPHS: A SURVEY
• Weakly perfect graphs arising from rings
• Well-Covered Vector Spaces of Graphs
• Well-covered circulant graphs

Cited in

(13)

• On equistable, split, CIS, and related classes of graphs
• On graphs whose maximal cliques and stable sets intersect
• Detecting strong cliques
• Strong cliques in diamond-free graphs
• Strong cliques in vertex‐transitive graphs
• Edge-transitive lexicographic and Cartesian products
• Presentations for vertex-transitive graphs
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Unconditional reflexive polytopes
• On CIS circulants
• Graphs vertex-partitionable into strong cliques
• On Minkowski space and finite geometry
• A characterization of almost CIS graphs

This page was built for publication: Vertex-transitive CIS graphs

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