# Paired- and induced paired-domination in {E,net}-free graphs

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 3, page 473-485
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topOliver Schaudt. "Paired- and induced paired-domination in {E,net}-free graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 473-485. <http://eudml.org/doc/271009>.

@article{OliverSchaudt2012,

abstract = {
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study.
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₅\}-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₅\}-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₅\}-free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible.
},

author = {Oliver Schaudt},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; paired-domination; induced paired-domination; induced matchings; \{E,net\}-free graphs; -free graphs},

language = {eng},

number = {3},

pages = {473-485},

title = {Paired- and induced paired-domination in \{E,net\}-free graphs},

url = {http://eudml.org/doc/271009},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Oliver Schaudt

TI - Paired- and induced paired-domination in {E,net}-free graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 3

SP - 473

EP - 485

AB -
A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study.
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₅}-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₅}-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₅}-free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible.

LA - eng

KW - domination; paired-domination; induced paired-domination; induced matchings; {E,net}-free graphs; -free graphs

UR - http://eudml.org/doc/271009

ER -

## References

top- [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. Zbl1210.05093
- [2] A. Brandstädt and F.F. Dragan, On linear and circular structure of (claw, net)-free graphs, Discrete Appl. Math. 129 (2003) 285-303, doi: 10.1016/S0166-218X(02)00571-1. Zbl1032.05095
- [3] A. Brandstädt, F.F. Dragan and E. Köhler, Linear time algorithms for Hamiltonian problems on ( claw, net)-free graphs, SIAM J. Comput. 30 (2000) 1662-1677, doi: 10.1137/S0097539799357775. Zbl0973.05051
- [4] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F. Zbl0687.05033
- [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. Zbl1231.05199
- [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. Zbl1140.90479
- [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. Zbl0797.05076
- [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker New York, 1998). Zbl0890.05002
- [10] T.W. Haynes, L.M. Lawson and D.S. Studer, Induced-paired domination in graphs, Ars Combin. 57 (2000) 111-128. Zbl1064.05115
- [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 Zbl0997.05074
- [12] A. Kelmans, On Hamiltonicity of {claw, net}-free graphs, Discrete Math. 306 (2006) 2755-2761, doi: 10.1016/j.disc.2006.04.022. Zbl1106.05055
- [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. Zbl1238.05201
- [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. Zbl1257.05121
- [16] O. Schaudt, On weighted efficient total domination, J. Discrete Algorithms 10 (2012) 61-69, doi: 10.1016/j.jda.2011.06.001. Zbl1237.68092
- [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. Zbl1181.05074
- [19] B. Zelinka, Induced-paired domatic numbers of graphs, Math. Bohem. 127 (2002) 591-596. Zbl1003.05078

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.