general.hpp File Reference

Plans on strongly regular graphs. More...

Go to the source code of this file.

Detailed Description

Plans on strongly regular graphs.

  • An "srg-parameter-tuple" is a quadruple [n,k,a,c], where "n" is the number of vertices, "k" the (constant) vertex degree, "a" the (constant) number of common neighbours of adjacent vertices, and "c" the (constant) number of common neighbours of different non-adjacent vertices.
  • First we need a predicate "srg_p(G,t)", which checks whether graph G is of the type given by the srg-parameter-tuple t.
    1. This test should use "g2pghg" (see "Graphs as hypergraphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp.
    2. And the neighbour-sets should be computed when creating this hypergraph; see "Memoisation for general graphs and multigraphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp.
  • A "design graph" is a strongly regular graph with a=c; we speak of "k-design graph" if a=c=k.
  • We also need to consider the more general notion of "distance-regular" graphs (strongly regular graphs are exactly the distance-regular graphs of diameter 2).
  • It seems that only graphs are considered in the literature; but we need to include graphs with loops (see "Exactly one common neighbour" below).
    1. And, additionally to potentially allowing loops, we should also consider "weak" forms of such notions, where for example regularity is not required.
    2. Perhaps we speak of "strongly regular graphs with loops" and "design graphs with loops", if we ask for regularity (where a loop is counted only once!) and that every two distinct(!) vertices have exactly a resp. c common neighbours (where "neighbours" are the adjacent vertices (including the vertex itself iff it has a loop)).
    3. These considerations are motivated by considering "polar incidence structures" (compare "Graphs as hypergraphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp).
    4. And we add "weak" if we drop the regularity condition.
Exactly one common neighbour
  • We consider here graphs where every two distinct vertices have exactly one common neighbour, motivated by Exercise 1J in [A Course in Combinatorics] (see ComputerAlgebra/docus/CourseCombinatorics_LintWilson/Chapter01.hpp).
  • This subject is further developed in Exercise 21Q there (see CourseCombinatorics_LintWilson/Chapter21.hpp).
  • Actually, considering graphs *with loops* is relevant here.
  • So we want to determine (if possible) the weak 1-design graphs with loops (see above).
  • It is currently (31.7.2008) an exercise for MG,ML to determine the structure of such graphs with loops.
    1. We know already that if there is no vertex v_0 neighbour to all other vertices, and there are no loops, then such graphs are regular.
    2. If there is such v_0, what are the possible graphs?
  • Translating the search for such graphs into generalised SAT problems yields a hopefully useful generator:
    1. n is the parameter, and the boolean variables are (naturally) the edges.
    2. Translating the conditions "at most one common neighbour" and "at least one common neighbour" naturally yields propositional formulas.
    3. These can be solved directly, or translated to CNF.
    4. The condition about the non-existence of v_0 (see above) yields easily (long) clauses.

Definition in file general.hpp.