Vertex Clique Covering Numbers Of $r$-Regular $(r-2)$-Edge-Connected Graphs

Abstract

Let $G$ be a finite simple graph. 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$. In this paper, we study the function $vcc(G)$ for the case when $G$ is $r$-regular and $(r-2)$-edge-connected. A sharp upper bound for $vcc(G)$ is determined. Further, the set of possible values of $vcc(G)$ when $G$ is a $4$-regular connected graph is determined.