Geodesic
Paired- and induced paired-domination in {E,net}-free graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 473-485.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination, paired-domination, induced paired-domination, induced matchings, {E,net}-free graphs 
@article{DMGT_2012_32_3_a7,
     author = {Schaudt, Oliver},
     title = {Paired- and induced paired-domination in {{E,net}-free} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {473--485},
     publisher = {mathdoc},
     volume = {32},
     number = {3},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a7/}
}
TY  - JOUR
AU  - Schaudt, Oliver
TI  - Paired- and induced paired-domination in {E,net}-free graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 473
EP  - 485
VL  - 32
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a7/
LA  - en
ID  - DMGT_2012_32_3_a7
ER  - 
%0 Journal Article
%A Schaudt, Oliver
%T Paired- and induced paired-domination in {E,net}-free graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 473-485
%V 32
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a7/
%G en
%F DMGT_2012_32_3_a7
Schaudt, Oliver. Paired- and induced paired-domination in {E,net}-free graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 473-485. http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a7/

[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 (claw, net)-free graphs, Discrete Appl. Math. 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 ( claw, net)-free graphs, SIAM J. Comput. 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:3199::AID-NET4>3.0.CO;2-F

[12] A. Kelmans, On Hamiltonicity of {claw, net}-free graphs, Discrete Math. 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.