3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ If you can do it with $4b-5$ vertices, then I think you would have solved the Hadamard conjecture. $\endgroup$ Aug 26, 2012 at 16:42

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thanx for your reply, checking if this works.. $\endgroup$
    – tap1cse
    Aug 26, 2012 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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