Dominating cliques in chordal graphs
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.
scientific article; zbMATH DE number 562597
scientific article