Abstract
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) |
---|---|
Pages (from-to) | 307-316 |
Number of pages | 10 |
Journal | Australasian Journal of Combinatorics |
Volume | 27 |
State | Published - Dec 1 2003 |