On the clique behavior and Hellyness of the complements of regular graphs

DOI10.1016/J.DISC.2022.113230MaRDI QIDQ2099476zbMATH OpenOpenAlexFDO

Authors Rafael Villarroel-Flores

Publication date 23 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clique graphsHelly property

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A collection of sets is intersecting, if any pair of sets in the collection has nonempty intersection. A collection of sets (mathcal{C}) has the Helly property if any intersecting subcollection has nonempty intersection. A graph is /Helly/ if the collection of maximal complete subgraphs of (G) has the Helly property. We prove that if (G) is a (k)-regular graph with (n) vertices such that (n>3k+sqrt{2k^{2}-k}), then the complement (�ar{G}) is not Helly. We also consider the problem of whether the properties of Hellyness and convergence under the clique graph operator are equivalent for the complement of (k)-regular graphs, for small values of (k).

Recommendations

• Helly's property for \(n\)-cliques and the degree of a graph
• Helly type theorem and graphs
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• Characterization and recognition of generalized clique-Helly graphs
• Graph-Theoretic Concepts in Computer Science

Cites work

• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 3641500 (Why is no real title available?)
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Blue-Empty Chromatic Graphs
• Characterization and recognition of generalized clique-Helly graphs
• Clique‐convergence is undecidable for automatic graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• On expansive graphs
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• The clique behavior of circulants with three small jumps.
• The clique operator on cographs and serial graphs
• The clique operator on matching and chessboard graphs
• Über iterierte Clique-Graphen

Cited in

(3)

• scientific article; zbMATH DE number 2096436 (Why is no real title available?)
• scientific article; zbMATH DE number 2096437 (Why is no real title available?)
• On the existence of critical clique-Helly graphs

This page was built for publication: On the clique behavior and Hellyness of the complements of regular graphs

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