Discussiones Mathematicae Graph Theory 32(3) (2012)
473-485

doi: 10.7151/dmgt.1617

in {

Oliver Schaudt
Institut für Informatik |

We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching a pendant vertex to each vertex of the path on three vertices) as induced subgraphs.
This graph class is a natural generalization of {*claw, net*}-free graphs, which are intensively studied with respect to their nice properties concerning domination and hamiltonicity.
We show that any connected {*E, net*}-free graph has a paired-dominating set that, roughly, contains at most half of the vertices of the graph.
This bound is a significant improvement to the known general bounds.

Further, we show that any {*E, net*, C_{5}}-free graph has an induced paired-dominating set, that is a paired-dominating set that forms an induced matching, and that such set can be chosen to be a minimum paired-dominating set.
We use these results to obtain a new characterization of {*E, net*, C_{5}}-free graphs in terms of the hereditary existence of induced paired-dominating sets.
Finally, we show that the induced matching formed by an induced paired-dominating set in a {*E, net*, C_{5}}-free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible.

**Keywords:** domination, paired-domination, induced paired-domination, induced matchings, *{** E, net**}*-free graphs

**2010 Mathematics Subject Classification:** 05C69.

[1] | G. Bacsó, Complete description of forbidden subgraphs in the structural domination problem, Discrete Math. 309 (2009) 2466--2472, doi: 10.1016/j.disc.2008.05.053. |

[2] | A. Brandstädt and F.F. Dragan, On linear and circular structure of , Discrete Appl. Math. (claw, net)-free graphs 129 (2003) 285--303, doi: 10.1016/S0166-218X(02)00571-1. |

[3] | A. Brandstädt, F.F. Dragan and E. Köhler, Linear time algorithms for Hamiltonian problems on , SIAM J. Comput. ( claw, net)-free graphs 30 (2000) 1662--1677, doi: 10.1137/S0097539799357775. |

[4] | K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97--102, doi: 10.1016/0166-218X(92)90275-F. |

[5] | P. Damaschke, Hamiltonian-hereditary graphs, manuscript (1990). |

[6] | P. Dorbec and S. Gravier, Paired-domination in subdivided star-free graphs, Graphs Combin. 26 (2010) 43--49, doi: 10.1007/s00373-010-0893-1. |

[7] | G. Finke, V. Gordon, Y.L. Orlovich and I.É. Zverovich, Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optimization 5 (2008) 584--593, doi: 10.1016/j.disopt.2007.11.010. |

[8] | D.L. Grinstead, P.J. Slater, N.A. Sherwani and N.D. Holmes, Efficient edge domination problems in graphs, Inform. Process. Lett. 48 (1993) 221--228, doi: 10.1016/0020-0190(93)90084-M. |

[9] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker New York, 1998). |

[10] | T.W. Haynes, L.M. Lawson and D.S. Studer, Induced-paired domination in graphs, Ars Combin. 57 (2000) 111--128. |

[11] | T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199--206, doi: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F. |

[12] | A. Kelmans, On Hamiltonicity of , Discrete Math. {claw, net}-free graphs 306 (2006) 2755--2761, doi: 10.1016/j.disc.2006.04.022. |

[13] | C.M. Mynhardt and M. Schurch, Paired domination in prisms of graphs, Discuss. Math. Graph Theory 31 (2011) 5--23, doi: 10.7151/dmgt.1526. |

[14] | Y.L. Orlovich and I.É. Zverovich, Maximal induced matchings of minimum/maximum size, manuscript (2004). |

[15] | O. Schaudt, Total domination versus paired-domination, Discuss. Math. Graph Theory 32 (2012) 435--447, doi: 10.7151/dmgt.1614. |

[16] | O. Schaudt, On weighted efficient total domination, J. Discrete Algorithms 10 (2012) 61--69, doi: 10.1016/j.jda.2011.06.001. |

[17] | J.A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1 (1994) 157--171. |

[18] | Z. Tuza, Hereditary domination in graphs: Characterization with forbidden induced subgraphs, SIAM J. Discrete Math. 22 (2008) 849--853, doi: 10.1137/070699482. |

[19] | B. Zelinka, Induced-paired domatic numbers of graphs, Math. Bohem. 127 (2002) 591--596. |

Received 29 March 2011

Revised 31 August 2011

Accepted 31 August 2011