A study on r-configurations - A resource assignment problem on graphs

Let G be an undirected graph with a set of vertices V and a set of edges E. Given an integer r, we assign at most r labels (representing "resources") to each vertex. We say that such an assignment is an r-configuration if, fo r each label c, the vertices labeled by c form a dominating set for G. In t his paper, we are interested in the maximum number, D-r(G), of labels that can be assigned to the vertices of graph G by an r-configuration. The decis ion problem "D-1(G) greater than or equal to K?" (known as the domatic numb er problem) is NP-complete. We first investigate D-r(G) for general graphs and establish bounds on D-r( G) in terms of D-1(G) and the minimum vertex degree of G. We then discuss D -r(G) for d-regular graphs. We clearly have D-r(G) less than or equal to r( d + 1). We show that the problem of testing if D-r(G) = r(d + 1) is solvabl e in polynomial time for d-regular graphs with \V\ = 2(d + 1), but is NP-co mplete for those with \V\ = a(d + 1) for some integer a greater than or equ al to 3. Finally, we discuss cubic (i.e., 3-regular) graphs. It is easy to show 2r less than or equal to D-r(G) less than or equal to 4r for cubic gra phs. We show that the decision problem for D-1(G) = K is co-NP-complete for K = 2 and is NP-complete for K = 4. Although there are many cubic graphs G with D-1(G) = 2, surprisingly, every cubic graph has a 2-configuration wit h five labels, i.e., D-2(G) greater than or equal to 5 and such a 2-configu ration can be constructed in polynomial time. We use this fact to show D-r( G) greater than or equal to right perpendicular 5r/2 left perpendicular in general.