Vertex-transitive CIS graphs

DOI10.1016/J.EJC.2014.09.007zbMATH Open1302.05077arXiv1405.7874OpenAlexW1995147377MaRDI QIDQ472401FDOQ472401

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)

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.

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

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

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)

Cites Work

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