1
$\begingroup$

Given a positive integer $c>1$, for what parameters $(v,k,\lambda,\mu)$ does there exist a $c k$ regular graph on $v$ vertices that can be given an edge coloring with $c$ colors, such that the edges corresponding to each color form a $(v,k,\lambda,\mu)$ strongly regular graph?

For what parameters is the $c$-edge-colored $c k$ regular graph unique up to isomorphism?

Are there any known results, is there any literature on this topic?

This question is related to the questions asked recently at a meeting in Banff, for the case $c=2$.

$\endgroup$
1
$\begingroup$

Such objects are closely related to amorphic association schemes; these are association schemes for which any merging of classes is again an association scheme.Such an object often leads to an object in the question (and there are quite often many non-isomorphic examples). Here is a link to a survey (published in J.Comb.Th.(A)).

Moreover, for $c\leq 3$ one always gets an amorphic association scheme. For $c=2$ this is trivial, and for $n=3$ this is discussed in Sect. 7 of J.Comb.Th.(A).

PS. See also Strongly regular decompositions of the complete graph.

$\endgroup$
1
$\begingroup$

This is a construction for some examples, for c = 2 when the union of the two strongly regular graphs is the complete graph.

If there exists a skew-Hadamard matrix $H$ of order 4t, then the incidence matrix of the associated 2-(4t-1, 2t-1, t-1) design $D$ associated with $H$ is disjoint from the incidence matrix of its transpose. So $D$ and $D^{\ast}$ form a pair of strongly regular graphs satisfying the constraints of the question. Furthermore, if $H$ is equivalent to its transpose, then there exists a permutation $\sigma$ of the points of $D$ such that $D^{\sigma} = D^{\ast}$, which is an isomorphism of the complete graph swapping the edge colours in the terminology of the question. (The Paley type I Hadamard matrices give one infinite family of the type of phenomenon that you look for.)

I wrote a short note for the Bulletin of the Irish mathematical society a while ago which shows that this is the only such decomposition of the complete graph into two parts when $\lambda = \mu$. The link is here http://www.maths.tcd.ie/pub/ims/bull72/index.php

$\endgroup$
  • $\begingroup$ In the case of Question 2 of my Banff questions, I have now running a backtracking tree search to look for an automorphism of $\Delta_m$ that swaps the colours of the red and blue edges. I wrote the search in less than 100 lines of plain Python code, and it does not depend on graph libraries (e.g. Gephi, iGraph, NetworkX). The search finds the known automorphisms for $m=1,2,3,$ but fails to find one for $m=4.$ $\endgroup$ – Penguian Nov 8 '14 at 21:36
  • $\begingroup$ I have posted the Python source code for the search on Github in the Hadamard-fractious repository. I have also posted Cython code that is equivalent, but about 4 times faster. $\endgroup$ – Penguian Jan 2 '15 at 10:44
  • $\begingroup$ In the case of Question 2 of my Banff questions, I can now prove that the graphs given by the red and the blue edges are not isomorphic when m > 3. The proof uses Radon-Hurwitz theory to show that the maximum clique sizes of the two graphs differ. I will speak about this at the University of Newcastle and then write it up. $\endgroup$ – Penguian Mar 31 '15 at 4:00
  • $\begingroup$ I have now written up the proof. $\endgroup$ – Penguian Apr 14 '15 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.