Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs

DOI10.1137/S0895480194267853MaRDI QIDQ3128208zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Victor Chepoi, Feodor F. Dragan

Publication date 20 May 1997

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480194267853

zbMATH Keywords

chordal graphsdominationtree structuresclique packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Dominating cliques in chordal graphs
• The multiple domination and limited packing problems in graphs
• scientific article; zbMATH DE number 706830
• scientific article; zbMATH DE number 790422
• Clique packings and clique partitions of graphs without odd chordles cycles
• Packings by cliques and by finite families of graphs
• Distance paired-domination problems on subclasses of chordal graphs
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• On the arrangement of cliques in chordal graphs with respect to the cuts

Cited in

(18)

• Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths
• Weighted maximum-clique transversal sets of graphs
• Inapproximability of \(H\)-transversal/packing
• The clique-perfectness and clique-coloring of outer-planar graphs
• Signed and minus clique-transversal functions on graphs
• Detour trees
• Clique-perfectness of claw-free planar graphs
• Homogeneously orderable graphs
• On some graph classes related to perfect graphs: a survey
• Variations of maximum-clique transversal sets on graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
• Algorithms for finding clique-transversals of graphs
• Distance-hereditary graphs are clique-perfect
• Clique-perfectness of complements of line graphs
• Clique-perfectness of complements of line graphs
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Clique-perfectness and balancedness of some graph classes

This page was built for publication: Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs

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