A characterization of domination perfect graphs

Let \(G\) be finite and undirected graph without loops or multiple edges and let \(\gamma(G)\) and \(i(G)\) be its domination number and its independent domination number, respectively. \(G\) is called to be domination perfect if \(\gamma(H)=i(H)\) for every induced subgraph \(H\) of \(G\). For example line graphs and middle graphs are domination perfect (this is an implication of a more general theorem of Allan and Laskar). The main result of the present paper consists in a generalization of certain previously known properties of \(G\), and it is proved that \(G\) is domination perfect iff it does not contain four types of induced subgraphs which are pictured in this publication (Theorem 3). Further it is shown that an inequality relating \(\gamma(G)\) and \(i(G)\), which was proved for the class of \(K_{1,k}\)-free graphs \((k\geq 3)\) by Bollobás and Cockayne (Theorem 4), holds for such graphs \(G\) which do not contain two induced subgraphs \(K_{1,k}\) \((k\geq 3)\) having different centers and an edge in common (Theorem 5). By this theorem for some classes of graphs a substantially smaller upper bound for \(i(G)\) is given than by Theorem 4. This is shown by an example.

Recommendations

Cited in

(24)

This page was built for publication: A characterization of domination perfect graphs

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