7
$\begingroup$

Say two graphs are not isomorphic but are both strongly regular with the same set of parameters. Are there any parameters (other than the usual such as order, degrees, eigenvalues and multiplicities, etc.) that are determined, e.g., independence number, chromatic number, etc.?

Thanks for any help

Improve this question
$\endgroup$

5 Answers 5

Reset to default
10
$\begingroup$

It's a classic result that a graph parameter called Lovasz theta-function $\theta(\Gamma)$ of a strongly regular graph $\Gamma$ is determined by its parameters. And the significance of $\theta(\Gamma)$ is that it is "sandwiched" between the clique number and the chromatic number.

In more detail, the parameters of the s.r.g. $\Gamma$ determine a 3-dimensional commutative algebra of symmetric matrices (the adjacency matrix $A(\Gamma)$ of $\Gamma$, the adjacency matrix of its complement, and the identity matrix span this algebra). Anything that can be expressed in terms of this algebra, which is specified by the eigenvalues of $A(\Gamma)$, is a parameter you are asking about, and $\theta(\Gamma)$ is one of them. Another one is the number of spanning trees, as by Matrix Tree Theorem it is determined by the eigenvalues.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you suggest a standard reference for this fact? Thanks! $\endgroup$
    – Felix Goldberg
    Commented Dec 13, 2012 at 18:54
  • $\begingroup$ For s.r.g.'s? Say, designtheory.org/library/preprints/srg.pdf Or E.Bannai, T.Ito "Algebraic combinatorics I. Association schemes.", ISBN 978-0805304909. $\endgroup$
    – Dima Pasechnik
    Commented Dec 14, 2012 at 5:14
3
$\begingroup$

The number of cycles of length 3,4,5 are determined. If the girth is 4, the number of 6-cycles is determined too.

Improve this answer
$\endgroup$
2
$\begingroup$

It seems the girth of a strongly regular graph would be determined by its parameters in the following way. If $\lambda > 0$, then the girth is 3. If $\lambda=0$ and $\mu > 1$, then the girth is 4. If $\lambda=0$ and $\mu=1$ then the girth is 5. That last case is a little unusual...

Improve this answer
$\endgroup$
1
$\begingroup$

Okay, well, I checked Brouwer's website and combined that with the comment to the accepted answer of a question on this site. I checked the complement of the Shrikhande graph versus the complement of the line graph of $K_{4, 4}$ using Sage and found independence numbers of 3 and 4, and chromatic numbers of 6 and 4, respectively. Both are strongly regular with parameters (16, 9, 4, 6). So, that answers my question for some parameters.

They have the same girth though.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What about the girth of the Shrikhande graph vs $K_{4,4}$? $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 13, 2012 at 7:25
  • $\begingroup$ @aaron Also equal. Sorry, I was in a hurry last night so I didn't have time to say everything I should have said. $\endgroup$
    – GeoffDS
    Commented Dec 13, 2012 at 14:04
  • $\begingroup$ @aaron The reason I used the complements of those graphs was because the chromatic numbers and independence numbers were equal for the graphs themselves, all of those being 4. But, I did check the girth for all 4 and the pairs with same parameters had equal girth. $\endgroup$
    – GeoffDS
    Commented Dec 13, 2012 at 14:44
  • 1
    $\begingroup$ If the girth of a strongly regular graph is not three, it is four and the graph is bipartite. $\endgroup$
    – Chris Godsil
    Commented Dec 13, 2012 at 17:05
  • 1
    $\begingroup$ @chris The Petersen graph is strongly regular with girth 5... Did you say quite what you meant there? $\endgroup$
    – Louis Deaett
    Commented Dec 20, 2012 at 15:12
0
$\begingroup$

The diameter, energy and number of closed walks could be determined by parameters.

Improve this answer
$\endgroup$

You must log in to answer this question.

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