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

Oliver Schaudt

Discussiones Mathematicae Graph Theory (2012)

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

Abstract

top
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.

How to cite

top

Oliver 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. [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. [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. [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. [4] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F. Zbl0687.05033
  5. [5] P. Damaschke, Hamiltonian-hereditary graphs, manuscript (1990). 
  6. [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. [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. [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. [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker New York, 1998). Zbl0890.05002
  10. [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. [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. [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. [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. [14] Y.L. Orlovich and I.É. Zverovich, Maximal induced matchings of minimum/maximum size, manuscript (2004). 
  15. [15] O. Schaudt, Total domination versus paired-domination, Discuss. Math. Graph Theory 32 (2012) 435-447, doi: 10.7151/dmgt.1614. Zbl1257.05121
  16. [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. [17] J.A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1 (1994) 157-171. 
  18. [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. [19] B. Zelinka, Induced-paired domatic numbers of graphs, Math. Bohem. 127 (2002) 591-596. Zbl1003.05078

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.