Some Studies on Clique-free Sets of a Graph Using Clique Degree Conditions

Cliques are maximal complete subgraphs of a graph. A vertex v is said to vc-cover a clique C if v is in the clique C. A set S of vertices of a graph G is called a vc-covering set of G if every clique of G is vc-covered by some vertex in S. The cardinality of the smallest vc-covering set of G is called the vc-covering number, denoted as αvc(G). In this paper, we define new parameters such as strong (weak) vc-covering number and strong (weak) clique-free number, and we establish a relationship between them. We present an algorithm to find these numbers and obtain some bounds for the newly defined parameters. In addition, we define a partial order on the vertex set of a graph using clique degree conditions and study some of its properties.