Opened 12 years ago
Last modified 8 years ago
#9136 closed enhancement
more named graphs — at Version 10
Reported by: | mvngu | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | brunellus | 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
- Franklin graph --- #10322
- Balaban 10-cage
- Balaban 11-cage
- Double-star snark
- Ellingham–Horton 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 (10)
comment:1 Changed 12 years ago by
comment:2 Changed 11 years ago by
- Description modified (diff)
- Milestone set to sage-wishlist
comment:3 Changed 11 years ago by
- Description modified (diff)
comment:4 Changed 11 years ago by
- Description modified (diff)
comment:5 Changed 11 years ago by
- Description modified (diff)
comment:6 Changed 11 years ago by
- Description modified (diff)
comment:7 follow-up: ↓ 8 Changed 11 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 in reply to: ↑ 7 Changed 11 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 11 years ago by
- Description modified (diff)
comment:10 Changed 11 years ago by
- Description modified (diff)
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