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 ksubsets 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 Knesergraphs; see "Maxima package graphs" in ComputerAlgebra/Graphs/Lisp/plans/general.hpp) In the Maximagraphsdocumentation, 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:

Order of this group.

Explicit enumeration.

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.

Abstract representation through relations.

And also realising the generators through concrete automorphisms.

Is a formula known for the girth?

And for the precise degree of arctransitivity? This would imply the order of the automorphism group.

See http://en.wikipedia.org/wiki/Kneser_graph.

We should somewhere present a submodule with all the information available on the Petersengraph (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.