OKlibrary  0.2.1.6
Generators.hpp File Reference

Plans regarding generation of combinatorial graphs. More...

Go to the source code of this file.

## Detailed Description

Plans regarding generation of combinatorial graphs.

Todo:
Generalisations of the Kneser graphs
• The Johnson graphs J(n,k,i), consisting like the Kneser graphs of all k-subsets of n, while we have an edge joining two vertices if the intersection has exactly size i.
• The generalised Kneser graph K(n,k,t), the union of J(n,k,i) for 0 <= i < t.
• DONE (provided by kneser_g_hyp) The Kneser graph K(G) of a hypergraph G, with vertices the hyperedges, joined by an edge if disjoint.
• DONE (the graphs there are not the Kneser-graphs; see "Maxima package graphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp) In the Maxima-graphs-documentation, the Knesergraph K(n,m) is called "Petersen graph(N,m)", which is not right --- tell the mailing list.
Todo:
Parameters of the Kneser graphs
• Likely all relevant parameters regarding some generator should be made available where the generator is defined.
• Most famous for the Kneser graphs is the chromatic number.
• And then we have the automorphism group:
1. Order of this group.
2. Explicit enumeration.
3. A fundamental question here is whether, like for the Petersen graph, always the full permutation group of {1,...,n} induces all automorphisms of kneser_g(n,m).
• This is not the case for example for n=5, m=3, where there are no edges (and thus every permutation of powerset(setn(5),3) is an automorphism.
4. Abstract representation through relations.
5. And also realising the generators through concrete automorphisms.
• Is a formula known for the girth?
• And for the precise degree of arc-transitivity? This would imply the order of the automorphism group.
• See http://en.wikipedia.org/wiki/Kneser_graph.
• We should somewhere present a sub-module with all the information available on the Petersen-graph (for example the isomorphism from S_5 to its automorphism group, nice representations etc.; see above). As a part of the general tools for investigating Kneser graphs.
Todo:
Forms of complete graphs
• Create complete bipartite graphs.
• Create complete general graphs with k edges between two vertices.
• DONE Create complete graphs.

Definition in file Generators.hpp.