Dominating cliques in graphs
type: Item
instance of: scholarly article
title: Dominating cliques in graphs
zbMATH Open document ID: 0729.05043
DOI: 10.1016/0012-365X(90)90353-J
author: M. Cozzens
author: Laura L. Kelleher
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: A set of vertices in a graph is called a dominating set if every vertex not in the set of adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The authors discuss various conditions that suffice to guarantee the existence of a dominating clique. Furthermore, a polynomial algorithm is presented that finds a dominating clique in finite connected graphs with no induced \(P_ 5\) or \(C_ 5\). Finally, a forbidden subgraph characterization is given for a class of graphs that have a connected dominating set of size three.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4204390
zbMATH Keywords: dominating clique
zbMATH Keywords: forbidden subgraph
MaRDI profile type: MaRDI publication profile
cites work: Dominating sets for split and bipartite graphs
cites work: Dominating Sets in Chordal Graphs
cites work: Total domination in graphs
cites work: A linear algorithm for the domination number of a tree
cites work: Towards a theory of domination in graphs
cites work: Q4193514
cites work: `` Strong '' NP-Completeness Results
cites work: Q3328583
cites work: Parallel concepts in graph theory
cites work: Sufficient Conditions for Graphs to Have Threshold Number 2
cites work: Dominating sets in social network graphs
cites work: Q3340900
cites work: Optimum domination in weighted trees
cites work: Q3791195
cites work: Q3688433
cites work: A Note on "The Comparability Graph of a Tree"
cites work: The Complexity of the Partial Order Dimension Problem
full work available at URL: 0012-365x(90)90353-j
OpenAlex ID: W1985573889
Recommended article: Dominating cliques in graphs
Recommended article: Dominating cliques in \(P_ 5\)-free graphs
Recommended article: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
Recommended article: Q5461526
Recommended article: Dominating sets with small clique covering number
description: scientific article; zbMATH DE number 4204390