Dominating cliques in chordal graphs

DOI10.1016/0012-365X(94)90118-XMaRDI QIDQ1322189zbMATH OpenFDO

Authors Dieter Kratsch, Peter Damaschke, Anna Lubiw

Publication date 15 September 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)90118-X

zbMATH Keywords

chordchordal graphcyclediameterdominating cliquedominating setstrongly chordal graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Dominating cliques in graphs
• Dominating cliques in graphs
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• scientific article; zbMATH DE number 794265
• scientific article; zbMATH DE number 4134090
• Domination using induced cliques in graphs
• Clique domination in graphs.
• Domination in convex and chordal bipartite graphs
• Clique graph characterizations of strongly chordal graphs
• On covering all cliques of a chordal graph

Cites work

• Characterizations of strongly chordal graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• scientific article; zbMATH DE number 48751 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• Introduction to ``Topics on Domination
• On the Algorithmic Complexity of Total Domination
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(19)

• Clustering and domination in perfect graphs
• \(r\)-dominating cliques in graphs with hypertree structure
• A note on \(r\)-dominating cliques
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Maximum rooted connected expansion
• Stable structure on safe set problems in vertex-weighted graphs
• On dominating sets whose induced subgraphs have a bounded diameter
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• Maximum rooted connected expansion
• Dominating cliques in distance-hereditary graphs
• r-Domination problems on homogeneously orderable graphs
• Dominating cliques in graphs
• Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
• Diametral path graphs
• Graph Search Trees and Their Leaves
• On the leaves of graph search trees
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Fine-grained classification of detecting dominating patterns
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

This page was built for publication: Dominating cliques in chordal graphs

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