Regular clique covers of graphs

Dan Archdeacon, Dalibor Fronček, Robert Jajcay, Zdeněk Ryjáček, Jozef Širáň

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish (US)
Pages (from-to)307-316
Number of pages10
JournalAustralasian Journal of Combinatorics
StatePublished - Dec 1 2003


Dive into the research topics of 'Regular clique covers of graphs'. Together they form a unique fingerprint.

Cite this