Dominating cliques in chordal graphs
type: Item
instance of: scholarly article
title: Dominating cliques in chordal graphs
zbMATH Open document ID: 0796.05052
DOI: 10.1016/0012-365X(94)90118-X
author: Dieter Kratsch
author: Peter Damaschke
author: Anna Lubiw
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: A graph \(G\) is chordal if every cycle of length exceeding 3 has a chord, i.e. an edge joining two nonconsecutive vertices in the cycle. A chordal graph is called strongly chordal if every cycle of even length exceeding 5 has an odd chord, i.e. a chord joining two nonconsecutive vertices of odd distance apart in the cycle. This paper proves that a chordal graph has a dominating clique iff it has diameter at most 3 and proves (by means of a linear-time algorithm) that a strongly chordal graph which has a dominating clique has one as small as the smallest dominating set.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 562597
zbMATH Keywords: chord
zbMATH Keywords: cycle
zbMATH Keywords: chordal graph
zbMATH Keywords: dominating clique
zbMATH Keywords: diameter
zbMATH Keywords: strongly chordal graph
zbMATH Keywords: dominating set
MaRDI profile type: Publication
cites work: Q4099676
cites work: Characterizations of strongly chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Introduction to ``Topics on Domination''
cites work: Q3997600
cites work: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
cites work: On the Algorithmic Complexity of Total Domination
cites work: Doubly Lexical Orderings of Matrices
Recommended article: Dominating cliques in graphs
Recommended article: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
Recommended article: Q4847026
Recommended article: Q3035328
Recommended article: Domination using induced cliques in graphs
Recommended article: Q3115054
Recommended article: Domination in convex and chordal bipartite graphs
Recommended article: Q5401055
Recommended article: On covering all cliques of a chordal graph
description: scientific article; zbMATH DE number 562597