World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Note of Independent Number and Domination Number of Qn,k,m-Graph

    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 α(G), of a graph G(V,E) is the maximum cardinality of any subset SV(G) such that no two elements in S are adjacent in G. The domination number, denoted by γ(G), of a graph G(V,E) is the minimum cardinality of any subset SV(G) such that every vertex in V(G) is either in S or adjacent to an element of S. 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 Qn,k,m-graph, a common generalization of various popular interconnection networks. Besides, as by-products, we derive the independent number and domination number of (n,k)-star graph Sn,k, (n,k)-arrangement graph An,k, as well as three special graphs.

    References

    • 1. G. Lin, J. Guan and H. B. Feng, An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks, Physica A 500 (2018) 199–209. CrossrefGoogle Scholar
    • 2. M. M. D. Khomami et al., Minimum positive influence dominating set and its application in influence maximization: A learning automata approach, Applied Intelligence 48(3) (2018) 570–593. CrossrefGoogle Scholar
    • 3. X. Zhu et al., New dominating sets in social networks, J. Global Optimization 48 (2010) 633–642. CrossrefGoogle Scholar
    • 4. W. D. Chen, Dominating set problems in bi-swapped networks, Chinese Journal of Computer 39 (2016) 2512–2526. Google Scholar
    • 5. Y. C. Wei, F. G. Chen and H. X. Zhu, Independent number and dominating number of (n, k)-star graphs, Indonesian J. Electrical Engineering 11 (2013) 310–315. Google Scholar
    • 6. S. Klavžar and M. Ma, The domination number of exchanged hypercubes, Information Processing Lett. 114 (2014) 159–162. CrossrefGoogle Scholar
    • 7. P. K. Jha, A comment on the domination number of exchanged hypercubes, Information Processing Lett. 115 (2015) 343–344. CrossrefGoogle Scholar
    • 8. F. Harary and M. Livingston, Independent domination in hypercubes, Applied Mathematics Lett. 6 (1993) 27–28. CrossrefGoogle Scholar
    • 9. J.-M. Xu, Combinatorial Theory in Networks (Science Press, Beijing, 2013). Google Scholar
    • 10. P. K. Jha, 1-perfect codes over dual-cubes vis-à-vis Hamming codes over hypercubes, IEEE Transactions on Information Theory 61 (2015) 4259–4268. CrossrefGoogle Scholar
    • 11. Z. P. Li and J. Xu, A characterization of trees with equal independent domination and secure domination numbers, Information Processing Lett. 119 (2017) 14–18. CrossrefGoogle Scholar
    • 12. Y. X. Dong, E. F. Shan and L. Y. Kang, Constructing the minimum dominating sets of generalized de Bruijn digraphs, Discrete Mathematics 338 (2015) 1501–1508. CrossrefGoogle Scholar
    • 13. C. X. Kang, On domination number and distance in graphs, Discrete Applied Mathematics 200 (2016) 203–206. CrossrefGoogle Scholar
    • 14. W.-K. Chiang and R.-J. Chen, On the arrangement graph, Information Processing Lett. 66(4) (1998) 215–219. Crossref, ISIGoogle Scholar
    • 15. V. Zverovich, The k-tuple domination number revisited, Applied Mathematics 21 (2008) 1005–1011. Google Scholar
    • 16. L. Chen et al., On the [1, 2]-domination number of generalized Petersen graphs, Applied Mathematics and Computation 327 (2018) 1–7. CrossrefGoogle Scholar
    • 17. B. Neggazi et al., Efficient self-stabilizing algorithm for independent strong dominating sets in arbitrary graphs, Int. J. Foundations of Computer Science 26(6) (2015) 751–768. LinkGoogle Scholar
    • 18. W. Goddard and J. Lyle, Independent dominating sets in triangle-free graphs, J. Combinatorial Optimization 23 (2012) 9–20. CrossrefGoogle Scholar
    • 19. Z. Dvořák, 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 CrossrefGoogle Scholar
    • 20. S. K. Vaidya and N. J. Kothari, Some results on equi independent equitable dominating sets in graph, Journal of Scientific and Industrial Research 7(3) (2015) 77–85. CrossrefGoogle Scholar
    • 21. D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications, Springer Optimization and Its Applications (2012). CrossrefGoogle Scholar
    • 22. B. Brešar et al., On total domination in the Cartesian product of graphs, Discussiones Mathematicae Graph Theory. https://doi.org/10.7151/dmgt.2039 Google Scholar
    • 23. J. Cyman et al., Total domination versus domination in cubic graphs, Graphs and Combinatorics 34 (2018) 261–276. CrossrefGoogle Scholar
    • 24. E. Cheng and N. Shawash, A new decomposition scheme for generalized star graphs Sn,k and An,k, Congressus Numerantium 186 (2007) 145–159. Google Scholar
    • 25. E. Cheng and N. Shawash, Successive generalizations of star graphs, in 2012 Int. Symp. on Pervasive Systems, Algorithms and Networks, 11 (2012), pp. 65–69. CrossrefGoogle Scholar
    • 26. E. Cheng and N. Shawash, The Qn,k,m graph: A common generalization of various popular interconnection networks, Parallel Processing Lett. 23 (2013) 1350011. LinkGoogle Scholar
    • 27. X. Li et al., The reliability analysis based on subsystems of (n, k)-star graph, IEEE Transactions on Reliability 65(4) (2016) 1700–1709. CrossrefGoogle Scholar
    • 28. E. Cheng et al., On the problem of determining which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 33 (2017) 85–102. Crossref, ISIGoogle Scholar
    • 29. Y. Shang, R. Hao and M. Gu, Neighbor connectivity of two kinds of Cayley graphs, Acta Mathematicae Applicatae Sinica, English Series, 34(2) (2018) 386–397. CrossrefGoogle Scholar
    • 30. L. Lin et al., Conditional diagnosability of arrangement graphs under the PMC model, Theoretical Computer Science 548 (2014) 79–97. Crossref, ISIGoogle Scholar
    • 31. K. Day and A. Tripathi, Arrangement graphs: a class of generalized star graphs, Information Processing Lett. 42 (1992) 235–241. Crossref, ISIGoogle Scholar