A family of cliques in a graph G is said to be p-regular if any two cliques in the family intersect in exactly p vertices. A graph G is said to have a p-regular k-clique cover if there is a p-regular family H of k-cliques of G such that each edge of G belongs to a clique in H. Such a p-regular kclique cover is separable if the complete subgraphs of order p that arise as intersections of pairs of distinct cliques of H are mutually vertex-disjoint. For any given integers p, k, ℓ; p < k, we present bounds on the smallest order of a graph that has a p-regular k-clique cover with exactly ℓ cliques, and we describe all graphs that have p-regular separable k-clique covers with ℓ cliques.
|Original language||English (US)|
|Number of pages||10|
|Journal||Australasian Journal of Combinatorics|
|State||Published - Dec 1 2003|