Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2-domination number, γw2(G), the 2-domination number, γ2(G), the {2}-domination number, γ{2}(G), the double domination number, γ×2(G), the total {2}-domination number, γt{2}(G), and the total double domination number, γt×2(G), where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γR(G), and two classical parameters, the domination number, γ(G), and the total domination number, γt(G), we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. © 2017 Elsevier B.V.

Registro:

Documento: Artículo
Título:Domination parameters with number 2: Interrelations and algorithmic consequences
Autor:Bonomo, F.; Brešar, B.; Grippo, L.N.; Milanič, M.; Safe, M.D.
Filiación:Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación, Buenos Aires, Argentina
CONICET-Universidad de Buenos Aires. Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, Argentina
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Buenos Aires, Argentina
University of Primorska, UP IAM, Muzejski trg 2, Koper, SI-6000, Slovenia
University of Primorska, UP FAMNIT, Glagoljaška 8, Koper, SI-6000, Slovenia
Departamento de Matemática, Universidad Nacional del Sur, Bahía Blanca, Buenos Aires, Argentina
Palabras clave:2-domination; Approximation algorithm; Double domination; Graph domination; Inapproximability; Integer domination; Rainbow domination; Split graph; Total domination; Approximation algorithms; 2-domination; Double domination; Graph domination; Inapproximability; Integer domination; Rainbow dominations; Split graphs; Total domination; Graph theory
Año:2018
Volumen:235
Página de inicio:23
Página de fin:50
DOI: http://dx.doi.org/10.1016/j.dam.2017.08.017
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v235_n_p23_Bonomo

Referencias:

  • Acharya, B.D., Domination in hypergraphs II. New directions (2010) Advances in Discrete Mathematics and Applications: Mysore, 2008, Ramanujan Math. Soc. Lect. Notes Ser., 13, pp. 1-18. , Ramanujan Math. Soc. Mysore
  • Adabi, M., Targhi, E.E., Rad, N.J., Moradi, M.S., Properties of independent Roman domination in graphs (2012) Australas. J. Combin., 52, pp. 11-18
  • Anusuya, V., Kala, R., A note on disjoint dominating sets in graphs (2012) Int. J. Contemp. Math. Sci., 7 (41-44), pp. 2099-2110
  • Aram, H., Sheikholeslami, S.M., Volkmann, L., On the total {k}-domination and total {k}-domatic number of graphs (2013) Bull. Malays. Math. Sci. Soc. (2), 36 (1), pp. 39-47
  • Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M., (1999) Complexity and Approximation, p. xx+524. , Springer-Verlag Berlin
  • Barman, S.C., Mondal, S., Pal, M., Minimum 2-tuple dominating set of permutation graphs (2013) J. Appl. Math. Comput., 43 (1-2), pp. 133-150
  • Blidia, M., Chellali, M., Favaron, O., Ratios of some domination parameters in graphs and claw-free graphs (2007) Graph Theory in Paris, Trends Math., pp. 61-72. , Birkhäuser Basel
  • Brešar, B., Henning, M.A., Klavžar, S., On integer domination in graphs and Vizing-like problems (2006) Taiwanese J. Math., 10 (5), pp. 1317-1328
  • Brešar, B., Henning, M.A., Rall, D.F., Rainbow domination in graphs (2008) Taiwanese J. Math., 12 (1), pp. 213-225
  • Brešar, B., Kraner Šumenjak, T., On the 2-rainbow domination in graphs (2007) Discrete Appl. Math., 155 (17), pp. 2394-2400
  • Caro, Y., Pepper, R., Degree sequence index strategy (2014) Australas. J. Combin., 59, pp. 1-23
  • Chang, G.J., Li, B.-J., Wu, J., Rainbow domination and related problems on strongly chordal graphs (2013) Discrete Appl. Math., 161 (10-11), pp. 1395-1401
  • Chang, G.J., Wu, J., Zhu, X., Rainbow domination on trees (2010) Discrete Appl. Math., 158 (1), pp. 8-12
  • Chellali, M., Haynes, T.W., Hedetniemi, S.T., Bounds on weak roman and 2-rainbow domination numbers (2014) Discrete Appl. Math., 178, pp. 27-32
  • Chellali, M., Jafari Rad, N., On 2-rainbow domination and Roman domination in graphs (2013) Australas. J. Combin., 56, pp. 85-93
  • Chellali, M., Khelladi, A., Maffray, F., Exact double domination in graphs (2005) Discuss. Math. Graph Theory, 25 (3), pp. 291-302
  • Chlebík, M., Chlebíková, J., Approximation hardness of dominating set problems in bounded degree graphs (2008) Inform. and Comput., 206 (11), pp. 1264-1275
  • Choudhary, K., Margulies, S., Hicks, I.V., Integer domination of Cartesian product graphs (2015) Discrete Math., 338 (7), pp. 1239-1242
  • Cicalese, F., Milanič, M., Vaccaro, U., On the approximability and exact algorithms for vector domination and related problems in graphs (2013) Discrete Appl. Math., 161 (6), pp. 750-767
  • Cockayne, E.J., Dreyer, P.A., Jr., Hedetniemi, S.M., Hedetniemi, S.T., Roman domination in graphs (2004) Discrete Math., 278 (1-3), pp. 11-22
  • Cockayne, E.J., Hedetniemi, S.T., Towards a theory of domination in graphs (1977) Networks, 7 (3), pp. 247-261
  • DeLaViña, E., Goddard, W., Henning, M.A., Pepper, R., Vaughan, E.R., Bounds on the k-domination number of a graph (2011) Appl. Math. Lett., 24 (6), pp. 996-998
  • Desormeaux, W.J., Haynes, T.W., Vaughan, L., Double domination in complementary prisms (2013) Util. Math., 91, pp. 131-142
  • Dinur, I., Steurer, D., Analytical approach to parallel repetition (2014) Proceedings of the 2014 ACM Symposium on Theory of Computing, STOC’14, pp. 624-633. , ACM New York
  • Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegative data (1982) Math. Oper. Res., 7 (4), pp. 515-531
  • Domke, G.S., Hedetniemi, S.T., Laskar, R.C., Fricke, G., Relationships between integer and fractional parameters of graphs (1991) Graph Theory, Combinatorics, and Applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., pp. 371-387. , Wiley, New York
  • Dorbec, P., Hartnell, B., Henning, M.A., Paired versus double domination in K1,r-free graphs (2014) J. Comb. Optim., 27 (4), pp. 688-694
  • Dreyer, P.A., Jr., (2000) Applications and Variations of Domination in Graphs, p. 178. , (Ph.D. Thesis) ProQuest LLC, Rutgers The State University of New Jersey Ann Arbor, MI, New Brunswick
  • Favaron, O., Hansberg, A., Volkmann, L., On k-domination and minimum degree in graphs (2008) J. Graph Theory, 57 (1), pp. 33-40
  • Feige, U., A threshold of lnn for approximating set cover (1998) J. ACM, 45 (4), pp. 634-652
  • Fernau, H., Roman domination: a parameterized perspective (2008) Int. J. Comput. Math., 85 (1), pp. 25-38
  • Fink, J.F., Jacobson, M.S., n-domination in graphs (1985) Graph Theory with Applications To Algorithms and Computer Science (Kalamazoo, Mich., 1984), pp. 283-300. , Wiley-Intersci. Publ. Wiley, New York
  • Földes, S., Hammer, P.L., Split graphs having Dilworth number two (1977) Canad. J. Math., 29 (3), pp. 666-672
  • Fujita, S., Furuya, M., Difference between 2-rainbow domination and Roman domination in graphs (2013) Discrete Appl. Math., 161 (6), pp. 806-812
  • Furuya, M., A note on total domination and 2-rainbow domination in graphs (2015) Discrete Appl. Math., 184, pp. 229-230
  • Gairing, M., Hedetniemi, S., Kristiansen, P., McRae, A., Self-Stabilizing algorithms for {k}-domination (2003) Self-Stabilizing Systems, Lecture Notes in Computer Science, 2704, pp. 49-60. , Huang S.-T. Herman T. Springer Berlin Heidelberg
  • Gallai, T., Gráfokkal kapcsolatos maximum-minimum tételek (I. rész) (1957) Magyar Tud. Akad. Mat. Fiz. Oszt. Közl., 7, pp. 305-338
  • Gallai, T., Gráfokkal kapcsolatos maximum-minimum tételek (II. rész) (1958) Magyar Tud. Akad. Mat. Fiz. Oszt. Közl., 8, pp. 1-40
  • Gallai, T., Maximum-minimum sätze über graphen (1958) Acta Math. Acad. Sci. Hungar., 9, pp. 395-434
  • Gallai, T., Über extreme punkt- und kantenmengen (1959) Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 2, pp. 133-138
  • Garey, M.R., Johnson, D.S., A guide to the theory of NP-completeness (1979) Computers and Intractability, A Series of Books in the Mathematical Sciences, p. x+338. , W. H. Freeman and Co. San Francisco, Calif
  • Hansberg, A., Pepper, R., On k-domination and j-independence in graphs (2013) Discrete Appl. Math., 161 (10-11), pp. 1472-1480
  • Harary, F., Haynes, T.W., Nordhaus-Gaddum inequalities for domination in graphs (1996) Discrete Math., 155 (1-3), pp. 99-105. , Combinatorics, (Acireale, 1992)
  • Harary, F., Haynes, T.W., Double domination in graphs (2000) Ars Combin., 55, pp. 201-213
  • Hartnell, B.L., Rall, D.F., On dominating the Cartesian product of a graph and K2 (2004) Discuss. Math. Graph Theory, 24 (3), pp. 389-402
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., (1998) Domination in Graphs. Advanced Topics, Monographs and Textbooks in Pure and Applied Mathematics, 209, p. xiv+497. , Marcel Dekker, Inc. New York
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., (1998) Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, 208, p. xii+446. , Marcel Dekker, Inc. New York
  • Haynes, T.W., Slater, P.J., Paired-domination in graphs (1998) Networks, 32 (3), pp. 199-206
  • Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.C., Markus, L., Slater, P.J., Disjoint dominating sets in graphs (2008) Discrete Mathematics, Ramanujan Math. Soc. Lect. Notes Ser., 7, pp. 87-100. , Ramanujan Math. Soc. Mysore
  • Hedetniemi, S.T., Rubalcaba, R.R., Slater, P.J., Walsh, M., Few compare to the great Roman empire (2013) Congr. Numer., 217, pp. 129-136
  • Henning, M.A., Hedetniemi, S.T., Defending the Roman Empire—a new strategy (2003) Discrete Math., 266 (1-3), pp. 239-251
  • Henning, M.A., Kazemi, A.P., k-tuple total domination in graphs (2010) Discrete Appl. Math., 158 (9), pp. 1006-1011
  • Henning, M.A., Löwenstein, C., Rautenbach, D., Remarks about disjoint dominating sets (2009) Discrete Math., 309 (23-24), pp. 6451-6458
  • Henning, M.A., Yeo, A., Strong transversals in hypergraphs and double total domination in graphs (2010) SIAM J. Discrete Math., 24 (4), pp. 1336-1355
  • Henning, M.A., Yeo, A., 2-colorings in k-regular k-uniform hypergraphs (2013) European J. Combin., 34 (7), pp. 1192-1202
  • Henning, M.A., Yeo, A., (2013) Total Domination in Graphs, Springer Monographs in Mathematics, p. xiv+178. , Springer New York
  • Hou, X., Lu, Y., On the {k}-domination number of Cartesian products of graphs (2009) Discrete Math., 309 (10), pp. 3413-3419
  • John, N., Suen, S., Graph products and integer domination (2013) Discrete Math., 313 (3), pp. 217-224
  • Jose, B.K., Tuza, Z., Hypergraph domination and strong independence (2009) Appl. Anal. Discrete Math., 3 (2), pp. 347-358
  • Klasing, R., Laforest, C., Hardness results and approximation algorithms of k-tuple domination in graphs (2004) Inform. Process. Lett., 89 (2), pp. 75-83
  • Krzywkowski, M., On trees with double domination number equal to 2-domination number plus one (2013) Houston J. Math., 39 (2), pp. 427-440
  • Kulli, V.R., Inverse domination and inverse total domination in digraphs (2014) Int. J. Adv. Res. Comput. Sci. Technol., 2 (1), pp. 106-109
  • Li, N., Hou, X., On the total {k}-domination number of Cartesian products of graphs (2009) J. Comb. Optim., 18 (2), pp. 173-178
  • Liu, C.-H., Chang, G.J., Roman domination on 2-connected graphs (2012) SIAM J. Discrete Math., 26 (1), pp. 193-205
  • Liu, C.-H., Chang, G.J., Roman domination on strongly chordal graphs (2013) J. Comb. Optim., 26 (3), pp. 608-619
  • Löwenstein, C., Rautenbach, D., Pairs of disjoint dominating sets and the minimum degree of graphs (2010) Graphs Combin., 26 (3), pp. 407-424
  • Pavlič, P., Žerovnik, J., Roman domination number of the Cartesian products of paths and cycles (2012) Electron. J. Combin., 19 (3), p. 37. , Paper 19
  • Pilipczuk, M., Pilipczuk, M., Škrekovski, R., Some results on Vizing's conjecture and related problems (2012) Discrete Appl. Math., 160 (16-17), pp. 2484-2490
  • Pradhan, D., Algorithmic aspects of k-tuple total domination in graphs (2012) Inform. Process. Lett., 112 (21), pp. 816-822
  • Rad, N.J., Critical concept for 2-rainbow domination in graphs (2011) Australas. J. Combin., 51, pp. 49-60
  • Sampathkumar, E., Latha, L.P., Strong weak domination and domination balance in a graph (1996) Discrete Math., 161 (1-3), pp. 235-242
  • Schrijver, A., (2003) Combinatorial Optimization. Polyhedra and Efficiency (3 Volumes), Algorithms and Combinatorics, 24. , Springer–Verlag Berlin
  • Shang, W., Wang, X., Hu, X., Roman domination and its variants in unit disk graphs (2010) Discrete Math. Algorithms Appl., 2 (1), pp. 99-105
  • Shao, Z., Liang, M., Yin, C., Xu, X., Pavlič, P., Žerovnik, J., On rainbow domination numbers of graphs (2014) Inform. Sci., 254, pp. 225-234
  • Stewart, I., Defend the roman empire! (1999) Sci. Am., 281, pp. 136-139
  • Šumenjak, T.K., Rall, D.F., Tepeh, A., Rainbow domination in the lexicographic product of graphs (2013) Discrete Appl. Math., 161 (13-14), pp. 2133-2141
  • Vazirani, V.V., (2001) Approximation Algorithms, p. xx+378. , Springer-Verlag Berlin
  • Wolsey, L.A., An analysis of the greedy algorithm for the submodular set covering problem (1982) Combinatorica, 2 (4), pp. 385-393
  • Wu, Y., Xing, H., Note on 2-rainbow domination and Roman domination in graphs (2010) Appl. Math. Lett., 23 (6), pp. 706-709
  • Zelinka, B., Total domatic number of cacti (1988) Math. Slovaca, 38 (3), pp. 207-214
  • Zelinka, B., Domatic numbers of graphs and their variants: a survey (1998) Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 209, pp. 351-377. , Dekker New York

Citas:

---------- APA ----------
Bonomo, F., Brešar, B., Grippo, L.N., Milanič, M. & Safe, M.D. (2018) . Domination parameters with number 2: Interrelations and algorithmic consequences. Discrete Applied Mathematics, 235, 23-50.
http://dx.doi.org/10.1016/j.dam.2017.08.017
---------- CHICAGO ----------
Bonomo, F., Brešar, B., Grippo, L.N., Milanič, M., Safe, M.D. "Domination parameters with number 2: Interrelations and algorithmic consequences" . Discrete Applied Mathematics 235 (2018) : 23-50.
http://dx.doi.org/10.1016/j.dam.2017.08.017
---------- MLA ----------
Bonomo, F., Brešar, B., Grippo, L.N., Milanič, M., Safe, M.D. "Domination parameters with number 2: Interrelations and algorithmic consequences" . Discrete Applied Mathematics, vol. 235, 2018, pp. 23-50.
http://dx.doi.org/10.1016/j.dam.2017.08.017
---------- VANCOUVER ----------
Bonomo, F., Brešar, B., Grippo, L.N., Milanič, M., Safe, M.D. Domination parameters with number 2: Interrelations and algorithmic consequences. Discrete Appl Math. 2018;235:23-50.
http://dx.doi.org/10.1016/j.dam.2017.08.017