×

A study of monopolies in graphs. (English) Zbl 1272.05149

Summary: In a graph \(G\), a set \(D\) of vertices is said to be a monopoly if any vertex \(v\in V(G)\setminus D\) has at least \(\deg(v)/2\) neighbors in \(D\). A strict monopoly is defined similarly when we replace \(\deg(v)/2\) by \(\deg(v)/2+1\) for any vertex \(v\) whose degree is even number. By the monopoly size (resp. strict monopoly size) of \(G\) we mean the smallest cardinality of a monopoly (resp. strict monopoly) in \(G\). We first discuss the basic bounds for the monopoly and strict monopoly size of graphs. In the second section we show relationships between matchings and monopolies and present some upper bounds for the monopoly and strict monopoly size of graphs in terms of the matching number of graphs. The third section is devoted to presenting some lower bounds for the monopoly size of graphs in terms of the even-girth and odd-girth of graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bermond J.-C., Bond J., Peleg D., Perennes S.: The power of small coalitions in graphs. Discrete Appl. Math. 127, 399-414 (2003) · Zbl 1025.68061 · doi:10.1016/S0166-218X(02)00241-X
[2] Bondy J.A., Murty U.S.R.: Graph Theory. Springer, Berlin (2008) · Zbl 1134.05001 · doi:10.1007/978-1-84628-970-5
[3] Dreyer P.A., Roberts F.S: Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math 157, 1615-1627 (2009) · Zbl 1163.92035 · doi:10.1016/j.dam.2008.09.012
[4] Favaron, O.: Global alliances and independent domination in some classes of graphs. Electron. J. Combin. 15 (2008) #R123 · Zbl 1165.05338
[5] Favaron O., Fricke G., Goddard W., Hedetniemi S.M., Hedetniemi S.T., Kristiansen P., Laskar R.C., Skaggs R.D: Offensive alliances in graphs. Discuss. Math. Graph Theory 24(2), 263-275 (2004) · Zbl 1064.05112 · doi:10.7151/dmgt.1230
[6] Fernau H., Rodriguez J.A., Sigarreta J.M: Offensive r-alliances in graphs. Discrete Appl. Math. 157, 177-182 (2009) · Zbl 1200.05157 · doi:10.1016/j.dam.2008.06.001
[7] Flocchini P., Kralovic R., Roncato A., Ruzicka P., Santoro N: On time versus size for monotone dynamic monopolies in regular topologies. J. Discrete Algorithms 1, 129-150 (2003) · Zbl 1074.68045 · doi:10.1016/S1570-8667(03)00022-4
[8] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T: Alliances in graphs. J. Combin. Math. Combin. Comput. 48, 157-177 (2004) · Zbl 1051.05068
[9] Lovász, L., Plummer, M.D.: Matching Theory. North Holland, Amsterdam (1986) · Zbl 0618.05001
[10] Mishra A., Rao S.B: Minimum monopoly in regular and tree graphs. Discrete Math. 306, 1586-1594 (2006) · Zbl 1116.05080 · doi:10.1016/j.disc.2005.06.036
[11] Peleg D.: Local majorities, coalitions and monopolies in graphs. Theoret. Comput. Sci. 282, 231-257 (2002) · Zbl 0997.68088 · doi:10.1016/S0304-3975(01)00055-X
[12] Rodriguez J.A., Sigarreta J.M: Offensive alliances in cubic graphs. Int. Math. Forum 1(36), 1773-1782 (2006) · Zbl 1116.05060
[13] Sigarreta J.M., Rodriguez J.A: On the global offensive alliance number of a graph. Discrete Appl. Math. 157, 219-226 (2009) · Zbl 1191.05072 · doi:10.1016/j.dam.2008.02.007
[14] Zaker M.: Bounds for chromatic number in terms of even-girth and booksize. Discrete Math. 311, 197-204 (2011) · Zbl 1225.05104 · doi:10.1016/j.disc.2010.10.016
[15] Zaker M.: On dynamic monopolies of graphs with general thresholds. Discrete Math. 312, 1136-1143 (2012) · Zbl 1238.05262 · doi:10.1016/j.disc.2011.11.038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.