Take the 2-minute tour ×

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

share|improve this question
If you can do it with $4b-5$ vertices, then I think you would have solved the Hadamard conjecture. –  Brendan McKay Aug 26 '12 at 16:42

2 Answers 2

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

share|improve this answer
thanx for your reply, checking if this works.. –  tap1cse Aug 26 '12 at 15:59

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.

share|improve this answer

Your Answer


