Clique-partitioned graphs

Grahame Erskine; Terry Griggs; Jozef Širáň

doi:10.1016/j.dam.2022.02.024

paper

Clique-partitioned graphs

arXiv:1809.00527 · doi:10.1016/j.dam.2022.02.024

Abstract

A graph $G$ of order $n v$ where $n \geq 2$ and $v \geq 2$ is said to be weakly $(n, v)$ -clique-partitioned if its vertex set can be decomposed in a unique way into $n$ vertex-disjoint $v$ -cliques. It is strongly $(n, v)$ -clique-partitioned if in addition, the only $v$ -cliques of $G$ are the $n$ cliques in the decomposition. We determine the structure of such graphs which have the largest possible number of edges.

arXiv comment16 pages