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??
2 Answers
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.
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
-
$\begingroup$ thanx for your reply, checking if this works.. $\endgroup$– tap1cseAug 26, 2012 at 15:59