hi, Dima! In my context, for every power of primes q, Brown's construction gives a graph with order q^2+q+1, maximum degree q+1, diameter 2. The graph is not a regular one. The degree sequence of the graph is [(q+1)^(q^2), q^(q+1)]. This Brown's construction gives known largest lower bounds for the degree-diameter problem for the case of diameter 2.
Is not this construction called "Brown's construction" in graph theory? yawara On Mon, Oct 10, 2016 at 8:52 PM, Dima Pasechnik <dimp...@gmail.com> wrote: > > > On Sunday, October 9, 2016 at 9:10:50 PM UTC, ni732...@gmail.com wrote: >> >> Brown's construction is the function which takes a finite field to a >> graph with diameter 2. >> http://www.emis.ams.org/journals/EJC/Surveys/ds14.pdf >> >> Is it available in the graph component of sagemath? >> > > I won't be surprised if it could be constructed as a subgraph of one of > many strongly regular graphs > known to Sage, but there is no direct way to build such a graph in Sage, > IMHO. > > The description of the adjacency in the link you provide is a bit too > brief to see what exactly it does, > but I think these graphs are also known as Erdős–Rényi graphs, from > P. Erdós, A. Rényi, V.T. Sós > On a problem of graph theory > Studia Sci. Math. Hungar., 1 (1966), pp. 215–235 > > Brown's paper was published in the same year: W.G. Brown > On graphs that do not contain a Thomsen graph > Canad. Math. Bull., 9 (1966), pp. 281–285 > > We published a paper where these graphs were considered, and I implemented > a construction of them in GAP, but not in Sage :-) > https://www.cs.ox.ac.uk/publications/publication7266-abstract.html > > Please feel free to cc me on the Sage ticket with an implementation, I'd > be glad to review it. > > Dima > > >> If not, I plan to implement it for sagemath. >> >> yawara >> > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
