×

Independent strong weak domination: a mathematical programming approach. (English) Zbl 1457.05075

Summary: Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) of vertices is a dominating set if every vertex in \(V-S\) is adjacent to at least one vertex of \(S\). The domination number is the minimum cardinality of a dominating set. Let \(u,v\in V \). Then, \(u\) strongly dominates \(v\) and \(v\) weakly dominates \(u\) if (i) \(uv\in E\) and (ii) \( \deg u\geq\deg v \). A subset \(D\) of \(V\) is a strong (weak) dominating set of \(G\) if every vertex in \(V-D\) is strongly (weakly) dominated by at least one vertex in \(D\). The strong (weak) domination number of \(G\) is the minimum cardinality of a strong (weak) dominating set. A set \(D\subseteq V\) is an independent (or stable) set if no two vertices of \(D\) are adjacent. The independent domination number of \(G\) (independent strong domination number, independent weak domination number, respectively) is the minimum size of an independent dominating set (independent strong dominating set, independent weak dominating set, respectively) of \(G\). In this paper, mathematical models are developed for the problems of independent domination and independent strong (weak) domination of a graph. Then test problems are solved by the GAMS software, the optima and execution times are implemented. To the best of our knowledge, this is the first mathematical programming formulations for the problems, and computational results show that the proposed models are capable of finding optimal solutions within a reasonable amount of time.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
65K05 Numerical mathematical programming methods
90C05 Linear programming

Software:

GAMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alber, J., Betzler, N. and Niedermeier, R., Experiments on data reduction for optimal domination in networks, Ann. Oper. Res.146 (2006) 105-117. · Zbl 1106.90011
[2] Chartrand, G. and Lesniak, L., Graphs and Digraphs, 4th edn. (Chapman and Hall, London, 2005). · Zbl 1057.05001
[3] Cockayne, E. J. and Hedetniemi, S. T., Independence graphs, Congr. Numer.X (1974) 471-491. · Zbl 0305.05114
[4] Cockayne, E. J. and Hedetniemi, S. T., Towards a theory of domination in graphs, Networks7 (1977) 247-261. · Zbl 0384.05051
[5] Cooper, C., Klasing, R. and Zito, M., Lower bounds and algorithms for dominating sets in web graphs, Int. Math.2 (2005) 275-300. · Zbl 1110.68095
[6] Dai, F. and Wu, J., On constructing \(k\)-connected \(k\)-dominating sets in wireless ad-hoc and sensor networks, J. Parall. Distrib. Comput.66(7) (2006) 947-958. · Zbl 1101.68003
[7] Domke, G. S., Hattingh, J. H., Markus, L. R. and Ungener, E., On parameters related to strong and weak domination in graphs, Discrete Math.258 (2002) 1-11. · Zbl 1007.05075
[8] Hattingh, J. H. and Henning, M. A., On strong domination in graphs, J. Combin. Math. Combin. Comput.26 (1998) 33-42. · Zbl 0963.05066
[9] Hattingh, J. H. and Laskar, R. C., On weak domination in graphs, Ars Combin.49 (1998) 205-216. · Zbl 0963.05097
[10] Hattingh, J. H. and Rautenbach, D., Further results on weak domination in graphs, Utilitas Math.61 (2002) 193-207. · Zbl 0999.05080
[11] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J. (eds.), Domination in Graphs: Advanced Topics (Marcel DekkerNew York, 1998). · Zbl 0883.00011
[12] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). · Zbl 0890.05002
[13] Rautenbach, D., Bounds on the weak domination number, Austral. J. Combin.18 (1998) 245-251. · Zbl 0914.05041
[14] Rautenbach, D., The influence of special vertices on the strong domination, Discrete Math.197/198 (1999) 683-690. · Zbl 0927.05062
[15] Rautenbach, D., Bounds on the strong domination number, Discrete Math.215 (2000) 201-212. · Zbl 0943.05060
[16] Rautenbach, D. and Zverovich, V. E., Perfect graphs of strong domination and independent strong domination, Discrete Math.226 (2001) 297-311. · Zbl 0972.05037
[17] Sampathkumar, E. and Latha, L. Pushpa, Strong weak domination and domination balance in a graph, Discrete Math.161 (1996) 235-242. · Zbl 0870.05037
[18] Uğurlu, O., Berberler, M. E. and Berberler, Z. N., Strong weak domination: A mathematical programming strategy, Bull. Int. Math. Virtual Institute9 (2019) 513-519. · Zbl 1463.90180
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.