regular graph construction Is there a construction of (2b-2)-regular graph with 4b-3 or 4b-4 vertices, such that no two vertices share more than (b-1) vertices??
 A: Partial answer: If 4b-3 is a prime power, then the Paley graph of 4b-3 vertices will have this property, see http://en.wikipedia.org/wiki/Paley_graph. 
A: I  do not have a general construction, but you might like playing around with
this idea.  Set k=b-1 and look to build a 4k+1 vertex 2k regular graph.
Begin with a cycle.  If k=1, the graph is finished.  Otherwise select a sequence
S that "works" to give the extra edges needed.  The sequence has 2k-2 integers
v_i so that,  choosing a direction on the cycle,  vertex v gets connected to the
vertex that is v_i edges further ahead in the cycle.  For k=1, the empty sequence
works to give a pentagon.  For k=2, the sequence 4,5 works (I think) to give
a nine pointed star inside a nonagon.  I have not checked this, but I think
the sequence 3,5,6,7 works for k=3.
Here a necessary condition is that S and its translates by adding 1 should
share at most k-1 members. 4,6,7,8 has two members in common with its
translate above, as does 5,7,8;9.
Gerhard "Seeing It With Shifty Eyes" Paseman, 2012.08.26
