0 Replies - 20700 Views - Last Post: 05 March 2016 - 04:08 PM

#1 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12647
  • View blog
  • Posts: 45,820
  • Joined: 27-December 08

Testing for Strongly Regular Graphs

Post icon  Posted 05 March 2016 - 04:08 PM

There is no known characterization of strongly regular graphs. The spectral conditions are necessary. That means, if a graph is not strongly regular, it will not satisfy the eigenvalue conditions. However, there may exist parameters which satisfy the strongly regular graph criterion but are not graphic. Constructing strongly regular graphs can be a research problem, such as in the case of Moore graphs. So the eigenvalue conditions are nice, easy checks.

I wrote the following code to automate a proof that there are exactly six strongly regular graphs on 10 vertices. It spits out the candidates, which are exactly the six in my comments. I have given constructions for each configuration. Note that L(K_{5}) is the line graph of K_{5}.
/**
 *
 * @author Michael Levet
 * @date 01/27/2016
 *
 * PROGRAM OUTPUT: 
 *  Candidate Strongly Regular Graphs on 10 Vertices: 
 *  (10, 1, 0,0)  - Perfect Matching (5K_{2})
 *  (10, 3, 0, 1) - Petersen Graph (Complement of L(K_{5})
 *  (10, 4, 3, 0) - 2K_{5}
 *  (10, 5, 0, 5) - K_{5, 5} (Complement of 2K_{5})
 *  (10, 6, 3, 4) - L(K_{5})
 *  (10, 8, 6, 8) - Cocktail Party graph CP(10) (Complement of 5K_{2})
 */

public class TestStronglyRegularGraphs {

    public static void main(String[] args) {

        System.out.println("Candidate Strongly Regular Graphs on 10 Nodes:");

        for (int degree = 1; degree < 9; degree++) {
            for (int kappa = 0; kappa <= degree; kappa++) {
                for (int mu = 0; mu <= degree; mu++) {
                    if (isSRGCandidate(10, degree, kappa, mu)) {
                        System.out.printf("(%d, %d, %d, %d)\n", 
                                10, degree, kappa, mu);
                    }
                }
            }
        }
    }

    /**
     * A Strongly Regular Graph SRG(n, d, \kappa, \mu) is a graph on n 
     * vertices that is d-regular. Furthermore, every pair of adjacent 
     * vertices share precisely \kappa neighbors, and every pair of 
     * non-adjacent vertices share \mu common neighbors. There is no known 
     * characterization of Strongly Regular Graphs. However, there are spectral 
     * necessary conditions.
     *
     * This method accepts parameters (n, d, \kappa, \mu) and tests if the
     * following necessary conditions are satisfied: (1) (n - d - 1)\mu = d(d -
     * \kappa - 1) (2) lambda_{2}, \lambda_{3} = 1/2 * [(\kappa - \mu) \pm
     * \sqrt{(\kappa - \mu)^{2} + 4 * (d - \mu)] are both integers (3) The
     * multiplicities of \lambda_{2}, \lambda_{3} = 1/2 * [n-1 \mp (2d +
     * (n-1)(\kappa - mu))/(\sqrt{(\kappa - \mu)^{2} + 4 * (d - \mu))] are both
     * integers
     *
     * @param numVertices
     * @param degree
     * @param kappa
     * @param mu
     * @return true iff conditions (1), (2), and (3) are all satisfied.
     */
    public static boolean isSRGCandidate(int numVertices, int degree, 
            int kappa, int mu) {

        //check condition (1) and return false if it isn't satisfied
        if ((numVertices - degree - 1) * mu != degree * (degree - kappa - 1)) {
            return false;
        }

        double delta = Math.sqrt((kappa - mu) * (kappa - mu) 
                + 4 * (degree - mu));
        int deltaInteger = (int) delta;

        // in order for conditions (2)-(3) to be satisfied, 
        // it is necessary that delta is an integer 
        if (delta != deltaInteger) {
            return false;
        }

        // In order for \lambda_{2}, \lambda_{3} to be integers
        // it is necessary for (kappa - mu \pm deltaInteger) to be 
        // even. It suffices to check if either kappa - mu + deltaInteger
        // or kappa - mu - deltaInteger are even, as they have the same parity
        if ((kappa - mu + deltaInteger) % 2 != 0) {
            return false;
        }

        // The multiplicities of the eigenvalues must 
        // be integers. So it is necessary that deltaInteger divides 
        // 2d - (n-1)(\kappa - \mu)
        int multNumerator = 2 * degree + (numVertices - 1) * (kappa - mu);
        if (multNumerator % deltaInteger != 0) {
            return false;
        }

        // The second check that the multiplicities of \lambda_{2}, \lambda_{3}
        // are integers examines whether (n-1) \mp 
        // [2d + (n-1)(\kappa - \mu)]/deltaInteger
        // are both even. It suffices to check one of them, as they both have 
        // the same parity.
        if ((9 - multNumerator / deltaInteger) % 2 != 0) {
            return false;
        }

        // if all of these checks pass, 
        // we have a candidate for a strongly regular graph
        return true;
    }
}



Is This A Good Question/Topic? 0
  • +

Page 1 of 1