Welcome to MathOverflow

Question

3

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

flag	asked Aug 26 at 14:46 tap1cse 49●3

2

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

Johan Wästlund · Answer 1 · 2012-08-26 15:58:42Z UTC

4

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.

answered Aug 26 at 15:58

Johan Wästlund
3,068●1●8●15

Gerhard Paseman · Answer 2 · 2012-08-26 15:37:32Z UTC

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

regular graph construction

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.