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).
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– ShahroozCommented Mar 17, 2013 at 12:09
-
1$\begingroup$ 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. $\endgroup$– Brendan McKayCommented Mar 17, 2013 at 13:46
Add a comment
|
1 Answer
$\begingroup$
(Added by J.O'Rourke). Here is the graph above, but with vertices labeled from $1$ to $32$ rather than $0$ to $31$:
$\endgroup$
7
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$:
-
-
$\begingroup$ The sparse6 string of the graph: ':_b?@d@fA
_eclHJ_GcGaDhJjeMfKLOaINgIKcE_KNTILdKQVfPRUcDHRbFVXaBPQeMOQ' $\endgroup$– joroCommented Mar 17, 2013 at 14:45 -
$\begingroup$ By the way, there are no Cayley graphs with these properties. $\endgroup$– user22090Commented Mar 17, 2013 at 15:30
-
$\begingroup$ 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. $\endgroup$– ShahroozCommented Mar 17, 2013 at 20:55
-
$\begingroup$ 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. $\endgroup$– user22090Commented Mar 18, 2013 at 2:43