Opened 12 years ago

Last modified 9 years ago

## #9136 closed enhancement

# more named graphs — at Version 9

Reported by: | Minh Van Nguyen | Owned by: | jason, ncohen, rlm |
---|---|---|---|

Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |

Component: | graph theory | Keywords: | |

Cc: | Lukáš Lánský | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description (last modified by )

The database of common graphs currently implements lots of named graphs. Here is a list of named graphs to add to that database:

- Bidiakis cube --- #10307
- Brinkmann graph --- #10310
- Butterfly graph --- #10313
- Friendship graph --- #10315
- Dürer graph --- #10316
- Errera graph --- #10321
- Balaban 10-cage
- Balaban 11-cage
- Double-star snark
- Ellingham–Horton graph
- Franklin graph
- fullerene graphs
- Goldner–Harary graph
- Grötzsch graph
- Harries–Wong graph
- Herschel graph
- Hoffman graph
- Holt graph
- Horton graph
- Kittell graph
- Markström graph
- McGee graph
- Meredith graph
- Moser spindle
- Sousselier graph
- Poussin graph
- Robertson graph
- Tutte's fragment
- Tutte graph
- Young–Fibonacci lattice
- Wagner graph
- Wiener-Araya graph
- Clebsch graph
- Hall–Janko graph
- Paley graph
- Shrikhande graph
- Möbius–Kantor graph
- Nauru graph
- Coxeter graph
- Tutte–Coxeter graph
- Dyck graph
- Foster graph
- Biggs–Smith graph
- Rado graph
- Folkman graph
- Gray graph
- Ljubljana graph
- Tutte 12-cage
- Blanuša snarks
- Szekeres snark
- Tietze's graph
- Watkins snark

### Change History (9)

### comment:1 Changed 12 years ago by

### comment:2 Changed 12 years ago by

Description: | modified (diff) |
---|---|

Milestone: | → sage-wishlist |

### comment:3 Changed 12 years ago by

Description: | modified (diff) |
---|

### comment:4 Changed 12 years ago by

Description: | modified (diff) |
---|

### comment:5 Changed 12 years ago by

Description: | modified (diff) |
---|

### comment:6 Changed 12 years ago by

Description: | modified (diff) |
---|

### comment:7 follow-up: 8 Changed 12 years ago by

Many of these graphs can be trivially generated in GAP using its package Grape (a part of the optional gap_packages spkg) and a library of primitive groups (a part of optional databases_gap spkg). E.g. here is how to get Schlaefli graph:

sage: gap.load_package('grape') sage: gap.eval('G:=NullGraph(PrimitiveGroup(27,12),27);') 'rec( isGraph := true, order := 27, group := PSp(4, 3), \n schreierVector := [ -1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, \n 2, 1, 1, 2, 2, 1, 1, 1, 2 ], adjacencies := [ [ ] ], \n representatives := [ 1 ], isSimple := true )' sage: gap.eval('AddEdgeOrbit(G,[1,2]);') '' sage: gap.eval('VertexDegrees(G);') '[ 10 ]' sage: edges=gap('Orbit(G.group,[1,2],OnSets)') sage: len(edges) 135 sage: schlaefli=Graph([[int(x[1])-1,int(x[2])-1] for x in edges]) sage: schlaefli.degree() [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10] sage: schlaefli.diameter() 2

IMHO there is a more fundamental issue here: Sage should handle such graphs in an efficient way --- just keeping all the edges is pretty much a waste, in particular for bigger examples with hundreds of vertices...

### comment:8 Changed 12 years ago by

Replying to dimpase:

Many of these graphs can be trivially generated in GAP using its package Grape (a part of the optional gap_packages spkg) and a library of primitive groups (a part of optional databases_gap spkg).

actually, Grape isn't even needed (I mentioned it for illustrative purposes): to construct the Sage graph, all you need is the following:

sage: edges=gap('Orbit(PrimitiveGroup(27,12),[1,2],OnSets)') sage: schlaefli=Graph([[int(x[1])-1,int(x[2])-1] for x in edges])

PS. To get e.g. Hall-Janko graph, use `PrimitiveGroup(100,1)`

...

### comment:9 Changed 12 years ago by

Description: | modified (diff) |
---|

**Note:**See TracTickets for help on using tickets.

My god O_O SO you are basically saying I'm not sending enough ? :-D

To be honest I have tried to implement some of them, but felt I should ask for the help of Sage's algebraists... This one, for example : is there any way to build it using Sage's tools ?

http://www.win.tue.nl/~aeb/graphs/Schlaefli.html

Nathann