Over-inflated graphs and the dominating set problem

Given a graph [Formula: see text] and a function [Formula: see text] satisfying [Formula: see text] for every [Formula: see text], the over-inflated graph[Formula: see text] of [Formula: see text] is obtained as follows: each vertex [Formula: see text] is replaced by a clique [Formula: see text] of size [Formula: see text] and each edge [Formula: see text] is replaced by an edge [Formula: see text] where [Formula: see text] such that different edges of [Formula: see text] are associated with non-adjacent edges of [Formula: see text]. If [Formula: see text] for every [Formula: see text], then we say that [Formula: see text] is the [Formula: see text]-inflated graph of [Formula: see text]. In this work, we present two characterizations of the over-inflated graphs, one of them leading to a linear-time recognition algorithm. Furthermore, we show that the dominating set problem is NP -complete for cubic line graphs of bipartite graphs and for planar bipartite [Formula: see text]-inflated graphs with girth at least [Formula: see text] for a fixed [Formula: see text].