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