Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Does there exist a regular graph of degree 4 having its diameter equal to three and its number of vertices equal to 32? What I know is http://www-ma4.upc.es/~comellas/delta-d/desc_g/desc_g3.html ( the second graph).

share|improve this question
    
By this address: mathworld.wolfram.com/QuarticGraph.html and a probabilistic program that I wrote in Maple (and with 20 min run, that I know it is very small time), I think there is not such a graph. It is interesting for me if such a graph exist. Also, I think Dear McKay with Naughty software, can help you more than me. Also, it is obvious that, such a graph (if it exist) is not strongly regular. –  Shahrooz Mar 17 '13 at 12:09
1  
Hi Shahrooz! I have two of order 30 and one of order 35. It would be strange if there is none of order 32, but I guess it is possible. –  Brendan McKay Mar 17 '13 at 13:46

1 Answer 1

up vote 8 down vote accepted

Here's an adjacency list, it's 4-regular, so there should be 4 vertices per line. I'm sure it will be easier for you to get the graph that for me to figure out the software interface here.

14 3 9 24 5 8 25 3 30 16 21 7 1 0 29 30 15 28 23 11 28 16 26 1 31 19 10 23 20 27 2 29 15 14 1 22 0 13 17 28 6 21 22 25 17 13 18 4 20 24 26 22 9 11 25 20 8 0 31 19 21 4 8 24 5 31 20 2 9 11 30 27 31 11 26 30 6 28 14 27 13 16 12 7 10 24 2 15 12 10 8 27 26 29 4 6 12 21 0 15 10 13 1 29 12 5 23 18 19 17 7 22 5 19 4 9 23 3 7 25 17 2 3 18 16 18 6 14

There appear to be many such graphs.


(Added by J.O'Rourke). Here is the graph above, but with vertices labeled from $1$ to $32$ rather than $0$ to $31$:
          Special Graph

share|improve this answer
    
Great. Confirmed. –  Brendan McKay Mar 17 '13 at 14:39
    
The sparse6 string of the graph: ':_b?@d@fA_eclHJ_GcGaDhJjeMfKLOaINgIKcE_KNTILdKQVfPRUcDHRbFVXaBPQeMOQ' –  joro Mar 17 '13 at 14:45
    
By the way, there are no Cayley graphs with these properties. –  geoffreyexoo Mar 17 '13 at 15:30
    
Very nice, dear geoffreyexoo, what was your strategy for finding this graph? I found some 4-regular graphs with diameter 4. Also by some papers that BOLLOBAS and his coworkers wrote, I think there are a little number of such graph that you found one of them. –  Shahrooz Mar 17 '13 at 20:55
    
The first 10 such graphs that I found were all different (not isomorphic), so I figured there are probably more than 10. The method is the same one I used to find some of the other graphs at the web site mentioned in the question. Roughly, it's this: pick a vertex, construct a tree of radius three degree four emanating from that vertex. Pick another vertex and repeat, using as many existing edges as possible, etc. When you get stuck, back up. It's 15 year old program and my memory of it is a bit hazy. –  geoffreyexoo Mar 18 '13 at 2:43

Your Answer

 
discard

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.