A Note of Independent Number and Domination Number of -Graph
Abstract
The independent number and domination number are two essential parameters to assess the resilience of the interconnection network of multiprocessor systems which is usually modeled by a graph. The independent number, denoted by , of a graph is the maximum cardinality of any subset such that no two elements in are adjacent in . The domination number, denoted by , of a graph is the minimum cardinality of any subset such that every vertex in is either in or adjacent to an element of . But so far, determining the independent number and domination number of a graph is still an NPC problem. Therefore, it is of utmost importance to determine the number of independent and domination number of some special networks with potential applications in multiprocessor system. In this paper, we firstly resolve the exact values of independent number and upper and lower bound of domination number of the -graph, a common generalization of various popular interconnection networks. Besides, as by-products, we derive the independent number and domination number of -star graph , -arrangement graph , as well as three special graphs.
References
- 1. , An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks, Physica A 500 (2018) 199–209. Crossref, Google Scholar
- 2. , Minimum positive influence dominating set and its application in influence maximization: A learning automata approach, Applied Intelligence 48(3) (2018) 570–593. Crossref, Google Scholar
- 3. , New dominating sets in social networks, J. Global Optimization 48 (2010) 633–642. Crossref, Google Scholar
- 4. , Dominating set problems in bi-swapped networks, Chinese Journal of Computer 39 (2016) 2512–2526. Google Scholar
- 5. , Independent number and dominating number of (n, k)-star graphs, Indonesian J. Electrical Engineering 11 (2013) 310–315. Google Scholar
- 6. , The domination number of exchanged hypercubes, Information Processing Lett. 114 (2014) 159–162. Crossref, Google Scholar
- 7. , A comment on the domination number of exchanged hypercubes, Information Processing Lett. 115 (2015) 343–344. Crossref, Google Scholar
- 8. , Independent domination in hypercubes, Applied Mathematics Lett. 6 (1993) 27–28. Crossref, Google Scholar
- 9. , Combinatorial Theory in Networks (Science Press, Beijing, 2013). Google Scholar
- 10. , 1-perfect codes over dual-cubes vis-à-vis Hamming codes over hypercubes, IEEE Transactions on Information Theory 61 (2015) 4259–4268. Crossref, Google Scholar
- 11. , A characterization of trees with equal independent domination and secure domination numbers, Information Processing Lett. 119 (2017) 14–18. Crossref, Google Scholar
- 12. , Constructing the minimum dominating sets of generalized de Bruijn digraphs, Discrete Mathematics 338 (2015) 1501–1508. Crossref, Google Scholar
- 13. , On domination number and distance in graphs, Discrete Applied Mathematics 200 (2016) 203–206. Crossref, Google Scholar
- 14. , On the arrangement graph, Information Processing Lett. 66(4) (1998) 215–219. Crossref, ISI, Google Scholar
- 15. , The k-tuple domination number revisited, Applied Mathematics 21 (2008) 1005–1011. Google Scholar
- 16. , On the [1, 2]-domination number of generalized Petersen graphs, Applied Mathematics and Computation 327 (2018) 1–7. Crossref, Google Scholar
- 17. , Efficient self-stabilizing algorithm for independent strong dominating sets in arbitrary graphs, Int. J. Foundations of Computer Science 26(6) (2015) 751–768. Link, Google Scholar
- 18. , Independent dominating sets in triangle-free graphs, J. Combinatorial Optimization 23 (2012) 9–20. Crossref, Google Scholar
- 19. , On distance r-dominating and 2r-independent sets in sparse graphs, J. Graph Theory 91(2) (2019) 99–246. https://doi.org/10.1002/jgt.22426 Crossref, Google Scholar
- 20. , Some results on equi independent equitable dominating sets in graph, Journal of Scientific and Industrial Research 7(3) (2015) 77–85. Crossref, Google Scholar
- 21. , Connected Dominating Set: Theory and Applications,
Springer Optimization and Its Applications (2012). Crossref, Google Scholar - 22. , On total domination in the Cartesian product of graphs, Discussiones Mathematicae Graph Theory. https://doi.org/10.7151/dmgt.2039 Google Scholar
- 23. , Total domination versus domination in cubic graphs, Graphs and Combinatorics 34 (2018) 261–276. Crossref, Google Scholar
- 24. , A new decomposition scheme for generalized star graphs and , Congressus Numerantium 186 (2007) 145–159. Google Scholar
- 25. , Successive generalizations of star graphs, in 2012 Int. Symp. on Pervasive Systems, Algorithms and Networks, 11 (2012), pp. 65–69. Crossref, Google Scholar
- 26. , The graph: A common generalization of various popular interconnection networks, Parallel Processing Lett. 23 (2013) 1350011. Link, Google Scholar
- 27. , The reliability analysis based on subsystems of (n, k)-star graph, IEEE Transactions on Reliability 65(4) (2016) 1700–1709. Crossref, Google Scholar
- 28. , On the problem of determining which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 33 (2017) 85–102. Crossref, ISI, Google Scholar
- 29. , Neighbor connectivity of two kinds of Cayley graphs, Acta Mathematicae Applicatae Sinica, English Series, 34(2) (2018) 386–397. Crossref, Google Scholar
- 30. , Conditional diagnosability of arrangement graphs under the PMC model, Theoretical Computer Science 548 (2014) 79–97. Crossref, ISI, Google Scholar
- 31. , Arrangement graphs: a class of generalized star graphs, Information Processing Lett. 42 (1992) 235–241. Crossref, ISI, Google Scholar


