As techniques for graph query processing mature, the need for optimization is increasinglybecoming an imperative. Indices are one of the key ingredients toward efficient queryprocessing strategies via cost-based optimization. Due to the apparent absence of a commonrepresentation model, it is difficult to make a focused effort toward developing accessstructures, metrics to evaluate query costs, and choose alternatives. In this context, recentinterests incovering-based graph matching appears to be a promising direction of research.In this paper, our goal is to formally introduce a new graph representation model, calledMinimum Hub Cover, and demonstrate that this representation offers interesting strategicadvantages, facilitates construction of candidate graphs from graph fragments, and helpsleverage indices in novel ways for query optimization. However, like other coveringproblems, minimum hub cover is NP-hard, and thus is a natural candidate for optimization.We claim that computing the minimum hub cover leads to substantial cost reduction forgraph query processing. We present a computational characterization of minimum hubcover based on integer programming to substantiate our claim and investigate itscomputational cost on various graph types.