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.

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.
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.
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.