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 alpha(G), of a graph G(V, E) is the maximum cardinality of any subset S subset of V(G) such that no two elements in S are adjacent in G. The domination number, denoted by gamma(G), of a graph G(V, E) is the minimum cardinality of any subset S subset of V(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 Q(n,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 S-n,S- k, (n, k)-arrangement graph A(n, k), as well as three special graphs.