Is Brown's construction available in the graph component of sagemath?

[ni732...@gmail.com]

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?
If not, I plan to implement it for sagemath.

yawara

[David Joyner]

On Sun, Oct 9, 2016 at 4:59 PM, <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 don't know but the Paley graph construction is in Sage. Is that
related to what you are talking about? You might look in the
graphs/generators/families.py module.

> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

[Dima Pasechnik]

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

[ywr nn]

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

--

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+unsubscribe@googlegroups.com.

[Dima Pasechnik]

On Wednesday, October 19, 2016 at 7:05:23 AM UTC+1, ywr nn wrote:

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?

Well, as I said, it was also discovered simultaneously and independently by Erdós and Rényi (see e.g. http://www.combinatorics.org/ojs/index.php/eljc/article/download/v22i2p21/pdf

for a short discussion on this)

Does this sound right to you?

Dima

yawara

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

[ni732...@gmail.com]

I just got it wrong.
I understand what you said and will implement Erdos-Renyi graph for sage.

Where can I read your GAP code?
I want to read it for study.

yawara