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.