ABSTRACT
Let G be a simple graph having a maximum matching M. The deficiency def(G) of G is the number of M-unsaturated vertices in G. The vertex clique covering number vcc(G) of G is the smallest number of cliques (complete subgraphs) needed to cover the vertex set of G. The problem that arises is that of determining the set of possible values of def(G) and vcc(G). In this paper we present a solution for the case of cubic graphs. An upper bound on def(G) is determined when G is k-regular.
