What graph parameters are determined by parameters for strongly regular graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:36:10Z http://mathoverflow.net/feeds/question/116220 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph What graph parameters are determined by parameters for strongly regular graph Graphth 2012-12-13T01:17:47Z 2012-12-21T11:39:46Z <p>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.?</p> <p>Thanks for any help</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116221#116221 Answer by Graphth for What graph parameters are determined by parameters for strongly regular graph Graphth 2012-12-13T01:46:58Z 2012-12-13T01:46:58Z <p>Okay, well, I checked Brouwer's website and combined that with the <a href="http://mathoverflow.net/questions/39312/smallest-non-isomorphic-strongly-regular-graphs" rel="nofollow">comment</a> 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.</p> <p>They have the same girth though.</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116261#116261 Answer by Dima Pasechnik for What graph parameters are determined by parameters for strongly regular graph Dima Pasechnik 2012-12-13T09:41:41Z 2012-12-20T17:10:53Z <p>It's a classic result that a graph parameter called <i>Lovasz theta-function</i> $\theta(\Gamma)$ of a strongly regular graph $\Gamma$ is determined by its parameters. And the significance of $\theta(\Gamma)$ is that it is <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1a1" rel="nofollow">"sandwiched"</a> between the clique number and the chromatic number.</p> <p>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.</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116872#116872 Answer by Louis Deaett for What graph parameters are determined by parameters for strongly regular graph Louis Deaett 2012-12-20T15:25:25Z 2012-12-20T15:25:25Z <p>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...</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116959#116959 Answer by Mohsen for What graph parameters are determined by parameters for strongly regular graph Mohsen 2012-12-21T10:28:12Z 2012-12-21T10:28:12Z <p>The diameter, energy and number of closed walks could be determined by parameters.</p> http://mathoverflow.net/questions/116220/what-graph-parameters-are-determined-by-parameters-for-strongly-regular-graph/116968#116968 Answer by Brendan McKay for What graph parameters are determined by parameters for strongly regular graph Brendan McKay 2012-12-21T11:39:46Z 2012-12-21T11:39:46Z <p>The number of cycles of length 3,4,5 are determined. If the girth is 4, the number of 6-cycles is determined too.</p>