Paired-domination in inflated graphs (Q596115)

The paper studies inflated graphs of graphs. If \(G\) is a graph, then the inflated graph \(G_I\) of \(G\) is defined. It is obtained from \(G\) by replacing each vertex \(x\) of \(G\) by a clique with the number of vertices equal to the degree of \(x\) in \(G\) and replacing each edge between two vertices by an edge joining vertices of these cliques, edges incident with one vertex being replaced by non-adjacent edges. A paired-dominating set of \(G\) is a subset \(S\) of the vertex set of \(G\) such that each vertex of \(G\) is in \(S\) or is adjacent to a vertex of \(S\) and, moreover, the subgraph of \(G\) induced by \(S\) contains a perfect matching. The minimum number of vertices of a paired-dominating set in \(G\) is the paired-domination number \(\gamma_p(G)\) of \(G\). The main result is the inequality \(n(G)\leq \gamma_p(G_I)\leq 4m(G)/[\delta(G)+ 1]\) for each graph \(G\) with \(\delta(G)\geq 2\). Here \(n(G)\), \(m(G)\), \(\delta(G)\) denote the number of vertices, the number of edges and the minimum degree of a vertex in \(G\). At the end of the paper inflated trees are studied. An algorithm for determining a minimum paired-dominating set in such a graph is described; it works in time \(O(n)\).