On _r_s(k)-perfect graphs

DOI10.1016/S0012-365X(02)00836-1MaRDI QIDQ1406558zbMATH OpenFDO

Authors Dieter Rautenbach, Lutz Volkmann

Publication date 4 September 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00836-1

zbMATH Keywords

distance domination numberdistance independence numberdomination perfect graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

For \(r\geq 1\), let \(\alpha_r\) and \(\gamma_r\) denote the \(r\)-distance-independence and \(r\)-distance-domination number, respectively. A graph \(G\) is \(\alpha_r\gamma_s(k)\)-perfect if \(\alpha_r(H)- \gamma_s(H)\leq k\) for every induced subgraph \(H\) of \(G\). In 1999, I. Zverovich characterized \(\alpha_1\gamma_1(k)\)-perfect graphs. The present authors characterize claw-free \(\alpha_2\gamma_2(k)\)-perfect graphs and \(\alpha_{2r-1}\gamma_r(k)\)-perfect graphs for \(r\geq 1\).

Recommendations

• A characterization of \(\Gamma\alpha(k)\)-perfect graphs
• \(i\gamma(1)\)-perfect graphs
• Some variations of perfect graphs
• scientific article; zbMATH DE number 5844229
• Distance perfectness of graphs

Cites work

• \(i\gamma(1)\)-perfect graphs
• A characterization of \(\Gamma\alpha(k)\)-perfect graphs
• A note on graphs which have upper irredundance equal to independence
• An induced subgraph characterization of domination perfect graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Contributions to the theory of domination, independence and irredundance in graphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 795022 (Why is no real title available?)
• Irredundance perfect andP6-free graphs
• Irredundance perfect graphs
• k-Bounded classes of dominant-independent perfect graphs
• Perfect graphs of strong domination and independent strong domination
• Stability, domination and irredundance in a graph
• The ratio of the irredundance number and the domination number for block-cactus graphs
• Upper domination and upper irredundance perfect graphs

Cited in

(7)

• scientific article; zbMATH DE number 1186103 (Why is no real title available?)
• Distance perfectness of graphs
• On the Co-P₃ -Structure of Perfect Graphs
• Induced regular perfect graphs
• Some variations of perfect graphs
• Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs
• Distance irredundance and connected domination numbers of a graph

This page was built for publication: On \(\alpha_{r}\gamma_{s}(k)\)-perfect graphs

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