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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Nov 8, 2014 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
    Commented Jan 2, 2015 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
    Commented Mar 31, 2015 at 4:00
  • $\begingroup$ I have now written up the proof. $\endgroup$
    – Penguian
    Commented Apr 14, 2015 at 6:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .