HaskellForMaths-0.4.1: Combinatorics, group theory, commutative algebra, non-commutative algebra

Math.Combinatorics.GraphAuts

Synopsis

# Documentation

isVertexTransitive :: Ord t => Graph t -> BoolSource

A graph is vertex-transitive if its automorphism group acts transitively on the vertices. Thus, given any two distinct vertices, there is an automorphism mapping one to the other.

isEdgeTransitive :: Ord t => Graph t -> BoolSource

A graph is edge-transitive if its automorphism group acts transitively on the edges. Thus, given any two distinct edges, there is an automorphism mapping one to the other.

isArcTransitive :: Ord t => Graph t -> BoolSource

A graph is arc-transitive (or flag-transitive) if its automorphism group acts transitively on arcs. (An arc is an ordered pair of adjacent vertices.)

isnArcTransitive :: Ord t => Int -> Graph t -> BoolSource

A graph is n-arc-transitive is its automorphism group is transitive on n-arcs. (An n-arc is an ordered sequence (v0,...,vn) of adjacent vertices, with crossings allowed but not doubling back.)

isDistanceTransitive :: Ord t => Graph t -> BoolSource

A graph is distance transitive if given any two ordered pairs of vertices (u,u') and (v,v') with d(u,u') == d(v,v'), there is an automorphism of the graph that takes (u,u') to (v,v')

graphAuts :: Ord a => Graph a -> [Permutation a]Source

Given a graph g, `graphAuts g` returns a strong generating set for the automorphism group of g.

Note that the implementation is currently only valid for connected graphs

incidenceAuts :: (Ord p, Ord b) => Graph (Either p b) -> [Permutation p]Source

Given the incidence graph of an incidence structure between points and blocks (for example, a set system), `incidenceAuts g` returns a strong generating set for the automorphism group of the incidence structure. The generators are represented as permutations of the points. The incidence graph should be represented with the points on the left and the blocks on the right.

Note that the implementation is currently only valid for connected incidence graphs