Detecting strong cliques

DOI10.1016/J.DISC.2019.06.010zbMATH Open1416.05269arXiv1808.08817OpenAlexW2963574048WikidataQ127638907 ScholiaQ127638907MaRDI QIDQ2312812FDOQ2312812

Authors: Ademir Hujdurović, Martin Milanič, Bernard Ries 

Publication date: 18 July 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.

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

Recommendations

• Strong cliques in diamond-free graphs
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Graphs vertex-partitionable into strong cliques
• scientific article; zbMATH DE number 4198027
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

zbMATH Keywords

line graphcubic graphNP-hardnesspolynomial-time algorithmstrong cliqueweakly chordal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Matching theory
• Normal hypergraphs and the perfect graph conjecture
• WELL-COVERED GRAPHS: A SURVEY
• Paths, Trees, and Flowers
• Some covering concepts in graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 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
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• A characterization and hereditary properties for partition graphs
• Equistable simplicial, very well-covered, and line graphs
• Strong cliques and equistability of EPT graphs
• Modeling \(k\)-coteries by well-covered graphs
• Equistarable bipartite graphs
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• On equistable, split, CIS, and related classes of graphs
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• Graph-Theoretic Concepts in Computer Science
• On the Complexity of Timetable and Multicommodity Flow Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity results for well‐covered graphs
• Local Structure When All Maximal Independent Sets Have Equal Weight
• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex-transitive CIS graphs
• Stochastic graphs and strongly perfect graphs - a survey
• A characterization of almost CIS graphs
• On split and almost CIS-graphs
• On CIS circulants
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• NP-completeness of edge-colouring some restricted graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Well covered simplicial, chordal, and circular arc graphs
• Title not available (Why is that?)
• On a conjecture of Meyniel
• On the perfect graph conjecture
• Graphs vertex-partitionable into strong cliques

Cited In (5)

• Finding a potential community in networks
• Strong cliques in diamond-free graphs
• Strong cliques in vertex‐transitive graphs
• Finding a strong stable set or a Meyniel obstruction in any graph
• Very large cliques are easy to detect

This page was built for publication: Detecting strong cliques

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