PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2012 | 32 | 3 | 473-485
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
473-485
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-03-29
poprawiono
2011-08-31
zaakceptowano
2011-08-31
Twórcy
autor
• Institut für Informatik, Universität zu Köln, Weyertal 80, 50931 Cologne, Germany
Bibliografia
• [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:3<199::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.
Typ dokumentu
Bibliografia
Identyfikatory