MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Partial answer: If 4b-3 is a prime power, then the Paley graph of 4b-3 vertices will have this property, see

share|cite|improve this answer

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|cite|improve this answer
thanx for your reply, checking if this works.. – tap1cse Aug 26 '12 at 15:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.