Title: 2-domination number for special classes of hypercubes, enhanced hypercubes and Knödel graphs

Authors: S. Arulanand; R. Sundara Rajan; S. Prabhu

Addresses: Department of Mathematics, Hindustan Institute of Technology and Science, Chennai – 603103, India ' Department of Mathematics, Hindustan Institute of Technology and Science, Chennai – 603103, India ' Department of Mathematics, Rajalakshmi Engineering College, Thandalam – 602105, India

Abstract: The system is fault-tolerant if, in the case that just one of the previously employed units fails, a different chain of units is utilised in its place. Because they provide the best fault tolerance, cycle-related graphs are employed in network analysis, periodic scheduling, and surface reconstruction. This can be achieved through a mathematical concept called domination. In a graph, each node has a minimum of one neighbour in a set, and then the set is called a dominating set of a network. A dominating set with the least cardinality is the domination number of the network. In this paper, we obtain the 2-domination number of some special classes of hypercubes, enhanced hypercubes, and Knödel graphs proving that the lower bound obtained in Fink and Jacobson (1985). quite precise, and also we prove that the time complexity of the 2-domination problem for the above graphs are linear.

Keywords: domination; 2-domination; hypercube; enhanced hypercube; Knödel graph; optimisation; time complexity.

DOI: 10.1504/IJNVO.2023.134993

International Journal of Networking and Virtual Organisations, 2023 Vol.29 No.2, pp.168 - 182

Received: 27 Jan 2023
Accepted: 22 Aug 2023
Published online: 23 Nov 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article