Opened 10 years ago

Closed 8 years ago

# Strongly Regular Graph

Reported by: Owned by: pgdx jason, ncohen, rlm major sage-duplicate/invalid/wontfix graph theory srg strongly regular graph ncohen Travis Scrimshaw N/A

I have been missing a function/method in the Graph class that allows you to test whether or not a graph is strongly regular.

A graph is strongly regular, or srg(n,k,l,m) if it is a regular graph on n vertices with degree k, and every two adjacent vertices have l common neighbours and every two non-adjacent vertices have m common neighbours. Examples are PetersenGraph? (10,3,0,1), the 5-Cycle (5,2,0,1), the Shrikhande graph (16,6,2,2) with more. For information on strongly regular graphs read on Wikipedia.

I have written a function, with documentation, that tests if a graph is strongly regular. The functions have optional arguments: n,k,l,m,certificate. More on this is to be found in the attached file.

The only thing that needs to be done is testing it and making it into a method of Graph, instead of a function, i.e. remove "g" from its argument list and rename all function calls g.* to this.*

Hope to see this path upstream as soon as possible.

I hereby give Sage community full copyright and other possible ownerships.

### Changed 10 years ago by pgdx

Source code containing function testing whether a graph is a Strongly Regular Graph (srg)

Patch

### comment:1 Changed 10 years ago by pgdx

I don't know if I should add a new patch, so I for now, just add a note here that we should use the parameter for is_regular, i.e.

```        if k is None:
if not this.is_regular():
return False
else:
if not this.is_regular(k):
return False

```

Also, this patch is maybe a bit slower then necessary; We fetch the neighbourhood of a vertex O(n²) times. This is simply because I don't know how to get the neighbourhood of a vertex, i.e. the vertices in its neighbourhood, not the edges it is adjacent to. The neighbourhood could be fetched in the beginning of the function, but I don't know how we deal with this kind of allocating a lot of memory.

### comment:2 Changed 10 years ago by pgdx

Furthermore, if the degree_iterator is somewhat slow, we could, since we are iterating through all vertices' neighbourhood anyway, skip that test in the beginning, and do it as we go.

### comment:3 Changed 8 years ago by chapoton

• Milestone set to sage-duplicate/invalid/wontfix

### comment:4 Changed 8 years ago by chapoton

• Status changed from new to needs_review

### comment:5 Changed 8 years ago by tscrim

• Authors changed from pgdx to Travis Scrimshaw
• Milestone changed from sage-duplicate/invalid/wontfix to sage-5.9

There's a small bug in `is_strongly_regular()` which I'm recycling this ticket for: the output block had one extra level of indentation so things like cliques would return `None` instead of `True` (or the parameters).

### comment:6 Changed 8 years ago by tscrim

• Description modified (diff)

For patchbot:

Apply: trac_10896-fix_strong_reg_graph-ts.patch

### comment:7 Changed 8 years ago by ncohen

• Milestone changed from sage-5.9 to sage-duplicate/invalid/wontfix
• Status changed from needs_review to positive_review

This is a duplicate of #14297 then.

Nathann

### comment:8 Changed 8 years ago by jdemeyer

• Authors Travis Scrimshaw deleted
• Reviewers set to Travis Scrimshaw

### comment:9 Changed 8 years ago by jdemeyer

• Resolution set to duplicate
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.