4
$\begingroup$

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$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Why 7? Do you have an example of a partial 5-resolution of size 7 for McL? $\endgroup$
    – Anurag
    Commented Jan 8, 2015 at 22:44
  • $\begingroup$ I might have misunderstood your question, but what you're asking isn't exactly en.wikipedia.org/wiki/Baranyai%27s_theorem ? $\endgroup$
    – domotorp
    Commented Jan 8, 2015 at 22:46
  • $\begingroup$ @domotorp I think that I need Baranyai's conclusion but for other hypergraphs than the complete ones. $\endgroup$
    – Felix Goldberg
    Commented Jan 8, 2015 at 22:50
  • $\begingroup$ Oh, yes, indeed. $\endgroup$
    – domotorp
    Commented Jan 8, 2015 at 23:09
  • 1
    $\begingroup$ @Anurag I don't have an example - I am hoping to construct one for an argument I am working on. Haemers and Tonchev say in the paper that they found five different spreads but don't say whether those spreads were pairwise disjoint. If you are interested (I thought you might be :) I'll be happy to disucss this further. $\endgroup$
    – Felix Goldberg
    Commented Jan 9, 2015 at 11:02

0

Reset to default

You must log in to answer this question.