Skip to main content
2 of 2
added 1 character in body
Felix Goldberg
  • 7k
  • 4
  • 31
  • 55

Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices).

A partial $k$-resolution of $G$ is a set of pairwise disjoint $k$-spreads of $G$.

Let us define the $k$-spread number $s_{k}(G)$ to be the maximum cardinality of a partial $k$-resolution of $G$.

Are there known facts about $s_{k}(G)$?

Motivation and more specific question

The definitions above are motivated by the concept of a spread in a strongly regular graph, introduced by Haemers & Tonchev in their 1996 paper. Their notion of a spread is a bit more special, in that they require the cliques to be Delsarte cliques (i.e. of the maximum allowed cardinality under the Delsarte/Hoffman spectral bound).

In particular, they show that the McLaughlin graph $McL$ (the unique $(275,112,30,56)$ strongly regular graph) has a spread in their sense. The Delsarte bound of $McL$ is $5$ so in my notation $s_{5}(McL) \geq 1$.

Is $s_{5}(McL)=7$?

Felix Goldberg
  • 7k
  • 4
  • 31
  • 55