Expanded-clique graphs and the domination problem
share
Given a graph G and a function f : V(G) →ℕ such that f(v_i) ≥ d(v_i) for every v_i ∈ V(G), where d(v_i) is the degree of v_i, the expanded-clique graph H of (G,f) exists and is defined as follows: for every v_i ∈ V(G), there is a set V_i ⊆ V(H) with f(v_i) vertices forming a clique, and d_G(v_i) vertices of V_i have a neighbor outside V_i, one in each V_j such that v_j ∈ N(v_i). In this work, we present two characterizations of the expanded-clique graphs. One of them leads to a linear-time algorithm of recognition. We show that given an expanded-graph H, the domination number of H plus the 2-independence number of the root G of H is equal to |V(G)|. We also show that the domination problem is -complete for some subclasses of the expanded-clique graphs.
READ FULL TEXT