Geodesic
Bounding the Open k-Monopoly Number of Strong Product Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 287-299.

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

Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈{ 1 − δ // 2 , . . ., δ // 2 } be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if δ_M (v) ≥δ G(v) 2+k, where δ_M(v) represents the number of neighbors of v in M and δ_G(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this article we study the open k-monopoly number of strong product graphs. We present general lower and upper bounds for the open k-monopoly number of strong product graphs. Moreover, we study in addition the open 0-monopolies of several specific families of strong product graphs.
Keywords: open monopolies, strong product graphs, alliances, domination 
@article{DMGT_2018_38_1_a22,
     author = {Kuziak, Dorota and Peterin, Iztok and Yero, Ismael G.},
     title = {Bounding the {Open} {k-Monopoly} {Number} of {Strong} {Product} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {287--299},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a22/}
}
TY  - JOUR
AU  - Kuziak, Dorota
AU  - Peterin, Iztok
AU  - Yero, Ismael G.
TI  - Bounding the Open k-Monopoly Number of Strong Product Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 287
EP  - 299
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a22/
LA  - en
ID  - DMGT_2018_38_1_a22
ER  - 
%0 Journal Article
%A Kuziak, Dorota
%A Peterin, Iztok
%A Yero, Ismael G.
%T Bounding the Open k-Monopoly Number of Strong Product Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 287-299
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a22/
%G en
%F DMGT_2018_38_1_a22
Kuziak, Dorota; Peterin, Iztok; Yero, Ismael G. Bounding the Open k-Monopoly Number of Strong Product Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 287-299. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a22/

[1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: Applications of Discrete Math., R.D. Ringeisen and F.S. Roberts (Ed(s)), (SIAM, Philadelphia, 1988) 189–199.

[2] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296. doi:10.1016/0095-8956(73)90042-7

[3] C. Dwork, D. Peleg, N. Pippenger and E. Upfal, Fault tolerance in networks of bounded degree, SIAM J. Comput. 17 (1988) 975–988. doi:10.1137/0217061

[4] H. Fernau, J.A. Rodríguez-Velázquez and J.M. Sigarreta, Global powerful r-alliances and total k-domination in graphs, Util. Math. 98 (2015) 127–147.

[5] P. Flocchini, R. Královič, A. Roncato, P. Ružička and N. Santoro, On time versus size for monotone dynamic monopolies in regular topologies, J. Discrete Algorithms 1 (2003) 129–150. doi:10.1016/S1570-8667(03)00022-4

[6] H. García-Molina and D. Barbara, How to assign votes in a distributed system, J. ACM 32 (1985) 841–860. doi:10.1145/4221.4223

[7] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition (CRC Press, Boca Raton, FL, 2011).

[8] K. Khoshkhah, M. Nemati, H. Soltani and M. Zaker, A study of monopolies in graphs, Graphs Combin. 29 (2013) 1417–1427. doi:10.1007/s00373-012-1214-7

[9] P. Kristiansen, S.M. Hedetniemi and S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004) 157–177.

[10] D. Kuziak, I. Peterin and I.G. Yero, Computing the ( k- ) monopoly number of direct product of graphs, Filomat 29 (2015) 1163–1171. doi:10.2298/FIL1505163K

[11] D. Kuziak, I. Peterin and I.G. Yero, On the monopolies of lexicographic product graphs: bounds and closed formulaes, Bull. Math. Soc. Sci. Math. Roumanie N.S. 59 (2016) 355–366.

[12] D. Kuziak, I. Peterin and I.G. Yero, Open k-monopolies in graphs: complexity and related concepts, Discrete Math. Theor. Comput. Sci. 18 (3) (2016).

[13] N. Linial, D. Peleg, Yu. Rabinovich and M. Saks, Sphere packing and local majorities in graphs, in: Proc. 2nd Israel Symposium on Theory and Computing Systems (Natanya, Israel, 1993) 141–149. doi:10.1109/ISTCS.1993.253475

[14] A. Mishra and S.B. Rao, Minimum monopoly in regular and tree graphs, Discrete Math. 306 (2006) 1586–1594. doi:10.1016/j.disc.2005.06.036

[15] D. Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoret. Comput. Sci. 282 (2002) 231–257. doi:10.1016/S0304-3975(01)00055-X

[16] I. Peterin, The complexity of open k-monopolies in graphs for negative k, manuscript (2016).

[17] G.F. Sullivan, Complexity of System-Level Fault Diagnosis and Diagnosability, Ph.D. Thesis (Yale University, New Haven, CT, USA, 1986).

[18] I.G. Yero and J.A. Rodríguez-Velázquez, A survey on alliances in graphs: defensive alliances, Util. Math. (2016), to appear.

[19] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math. 312 (2012) 1136–1143. doi:10.1016/j.disc.2011.11.038