Plans on strongly regular graphs.
More...
Go to the source code of this file.
Detailed Description
Plans on strongly regular graphs.
 Todo:
 Concepts

An "srgparametertuple" 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 nonadjacent vertices.

First we need a predicate "srg_p(G,t)", which checks whether graph G is of the type given by the srgparametertuple t.

This test should use "g2pghg" (see "Graphs as hypergraphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp.

And the neighboursets 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 "kdesign graph" if a=c=k.

We also need to consider the more general notion of "distanceregular" graphs (strongly regular graphs are exactly the distanceregular 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).

And, additionally to potentially allowing loops, we should also consider "weak" forms of such notions, where for example regularity is not required.

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

These considerations are motivated by considering "polar incidence
structures" (compare "Graphs as hypergraphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp).

And we add "weak" if we drop the regularity condition.
 Todo:
 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 1design 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.

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.

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:

n is the parameter, and the boolean variables are (naturally) the edges.

Translating the conditions "at most one common neighbour" and "at least one common neighbour" naturally yields propositional formulas.

These can be solved directly, or translated to CNF.

The condition about the nonexistence of v_0 (see above) yields easily (long) clauses.
Definition in file general.hpp.