On αrγs(k)-perfect graphs |
| |
Authors: | Dieter Rautenbach Lutz Volkmann |
| |
Institution: | aLehrstuhl II für Mathematik, RWTH Aachen, 52056 Aachen, Germany |
| |
Abstract: | For some integer k0 and two graph parameters π and τ, a graph G is called πτ(k)-perfect, if π(H)−τ(H)k for every induced subgraph H of G. For r1 let αr and γr denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α1γ1(k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study αrγs(k)-perfect graphs for r,s1. We prove several properties of minimal αrγs(k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α2r−1γr(k)-perfect graphs for r1. Furthermore, we characterize claw-free α2γ2(k)-perfect graphs. |
| |
Keywords: | Domination perfect graphs Domination Independence Distance domination number Distance independence number |
本文献已被 ScienceDirect 等数据库收录! |
|