[Up] [Previous] [Next] [Index]

4 Functions to determine regularity properties of graphs

Sections

  1. IsRegularGraph
  2. LocalParameters
  3. GlobalParameters
  4. IsDistanceRegular
  5. CollapsedAdjacencyMat
  6. OrbitalDigraphColadjMats
  7. VertexTransitiveDRGs

This chapter describes functions to determine regularity properties of graphs, and a function VertexTransitiveDRGs which determines the distance-regular graphs on which a given transitive permutation group acts as a vertex-transitive group of automorphisms.

4.1 IsRegularGraph

  • IsRegularGraph( gamma )

    This boolean function returns true if and only if the graph gamma is (out)regular.

    gap> IsRegularGraph( JohnsonGraph(4,2) );
    true
    gap> IsRegularGraph( EdgeOrbitsGraph(Group(()),[[1,2]],2) );
    false 
    

    4.2 LocalParameters

  • LocalParameters( gamma, V )
  • LocalParameters( gamma, V, G )

    Let gamma be a simple connected graph. Then this function determines all local parameters ci(V), ai(V), and bi(V) that gamma may have, with respect to the singleton vertex or nonempty list of vertices V. We say that gamma has the local parameter ci(V) (respectively ai(V), bi(V)), with respect to V, if the number of vertices at distance i-1 (respectively i, i+1) from V that are adjacent to a vertex w at distance i from V (see Distance) is the constant ci(V) (respectively ai(V), bi(V)) depending only on i and V (and not w).

    The function LocalParameters returns a list whose i-th element is the list [ci-1(V), ai-1(V), bi-1(V)], except that if some local parameter does not exist then -1 is put in its place.

    This function can be used to determine whether a given subset of the vertices of a graph is a distance-regular code in that graph.

    The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing V setwise. Including such a G can speed up the function.

    gap> gamma := JohnsonGraph(4,2);;
    gap> LocalParameters( gamma, 1 );
    [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> LocalParameters( gamma, [1,6] );
    [ [ 0, 0, 4 ], [ 2, 2, 0 ] ]
    gap> LocalParameters( gamma, [1,2] );
    [ [ 0, 1, 3 ], [ -1, -1, 0 ] ]
    

    4.3 GlobalParameters

  • GlobalParameters( gamma )

    Let gamma be a simple connected graph, and 0 lei le Diameter(gamma). This function determines all global parameters ci, ai, and bi that gamma may have. We say that gamma has the global parameter ci (respectively ai, bi) if the number of vertices at distance i-1 (respectively i, i+1) from a vertex v that are adjacent to a vertex w at distance i from v is the constant ci (respectively ai, bi) depending only on i (and not v and w).

    The function GlobalParameters returns a list of length Diameter(gamma)+1, whose i-th element is the list [ci-1, ai-1, bi-1], except that if some global parameter does not exist then -1 is put in its place.

    Note that gamma is distance-regular if and only if this function returns no -1 in place of a global parameter (see BCN89).

    See also LocalParameters and IsDistanceRegular.

    gap> gamma := JohnsonGraph(4,2);;
    gap> GlobalParameters( gamma );
    [ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
    gap> GlobalParameters( BipartiteDouble(gamma) );
    [ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ]
    

    4.4 IsDistanceRegular

  • IsDistanceRegular( gamma )

    This boolean function returns true if and only if gamma is distance-regular, i.e. gamma is simple, connected, and all global parameters ci,ai,bi exist for 0 lei leDiameter(gamma) (see BCN89).

    See also GlobalParameters.

    gap> gamma := JohnsonGraph(4,2);;
    gap> IsDistanceRegular( gamma );
    true
    gap> IsDistanceRegular( BipartiteDouble(gamma) );
    false 
    

    4.5 CollapsedAdjacencyMat

  • CollapsedAdjacencyMat( gamma )
  • CollapsedAdjacencyMat( G, gamma )

    The second form of this function returns the collapsed adjacency matrix for gamma, where the collapsing group is G. It is assumed that G is a subgroup of Aut(gamma).

    The (i,j)-entry of the collapsed adjacency matrix equals the number of edges in { [x,y]midy inj-th G-orbit}, where x is a fixed vertex in the i-th G-orbit.

    In the case where this function is given just one argument, then it must be a graph gamma with the property that gamma.group is transitive on the vertex-set of gamma. In this case, the returned collapsed adjacency matrix for gamma is with respect to the stabilizer in gamma.group of 1.

    The reader is warned that collapsed adjacency matrices can have different, but related meanings depending on the setting and the author.

    See also OrbitalDigraphColadjMats.

    gap> gamma := JohnsonGraph(4,2);
    rec( isGraph := true, order := 6,
      group := Group([ (1,4,6,3)(2,5), (2,4)(3,5) ]),
      schreierVector := [ -1, 2, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ],
      isSimple := true )
    gap> G := Stabilizer( gamma.group, [1,6], OnSets );;
    gap> CollapsedAdjacencyMat( G, gamma );
    [ [ 0, 4 ], [ 2, 2 ] ]
    gap> CollapsedAdjacencyMat( gamma );
    [ [ 0, 4, 0 ], [ 1, 2, 1 ], [ 0, 4, 0 ] ]
    

    4.6 OrbitalDigraphColadjMats

  • OrbitalDigraphColadjMats( G )
  • OrbitalDigraphColadjMats( G, H )

    This function returns a list of collapsed adjacency matrices for the orbital digraphs of the transitive permutation group G, collapsed with respect to Stabilizer(G,1), creating collapsed adjacency matrices for the orbital digraphs in the sense of PS97. These matrices are given with respect to some ordering of the orbits of Stabilizer(G,1) (the suborbits), with the trivial suborbit [1] coming first, and with the k-th matrix corresponding to the orbital digraph having the k-th suborbit as the adjacency of the vertex 1. The (i,j)-entry of the k-th matrix in the returned list equals the number of (directed) edges of the k-th orbital digraph that are in { [x,y]midy inj-th suborbit}, where x is a fixed vertex in the i-th suborbit.

    The optional parameter H, if included, should be equal to Stabilizer(G,1). The knowledge of this stabilizer may speed up the function.

    Prior to GRAPE 4.9.0 this function was called OrbitalGraphColadjMats, and for backward compatibility, this name will still work.

    The reader is warned that collapsed adjacency matrices can have different, but related meanings depending on the setting and the author. Note also that the k-th intersection matrix for the coherent configuration defined by G is the transpose of the collapsed adjacency matrix corresponding to the suborbit paired with the suborbit defining the k-th collapsed adjacency matrix for G. See Chapter 3 of Cam99.

    See also CollapsedAdjacencyMat.

    gap> G:=JohnsonGraph(5,3).group;;
    gap> OrbitalDigraphColadjMats(G);
    [ [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ], 
      [ [ 0, 6, 0 ], [ 1, 3, 2 ], [ 0, 4, 2 ] ], 
      [ [ 0, 0, 3 ], [ 0, 2, 1 ], [ 1, 2, 0 ] ] ]
    gap> C:=CyclicGroup(IsPermGroup,5);
    Group([ (1,2,3,4,5) ])
    gap> OrbitalDigraphColadjMats(C);
    [ [ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], 
          [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ] ], 
      [ [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], 
          [ 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0 ] ], 
      [ [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ], 
          [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ] ], 
      [ [ 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0 ], 
          [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ] ], 
      [ [ 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], 
          [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ] ] ]
    

    4.7 VertexTransitiveDRGs

  • VertexTransitiveDRGs( coladjmats )
  • VertexTransitiveDRGs( G )

    This function can determine (among other things) all the distance-regular graphs on which a given non-trivial transitive permutation group G acts as a vertex-transitive group of automorphisms (as long as the permutation rank of G is not too large).

    In the first form of this function, the input parameter coladjmats must be a list of collapsed adjacency matrices for the orbital digraphs of some non-trivial transitive permutation group G, collapsed with respect to a fixed point-stabilizer (such as the list of matrices produced by the function OrbitalDigraphColadjMats). It is assumed that the orbital/suborbit indexing used is the same as that for the rows (and columns) of each of the matrices, as well as for the indexing of the matrices themselves, with the trivial orbital first, so that, in particular, coladjmats[1] must be an identity matrix.

    In the second form of this function, the input parameter G must be a non-trivial transitive permutation group, and then the result returned will be the same as VertexTransitiveDRGs( OrbitalDigraphColadjMats( G ) ).

    In either case, this function returns a record result, which gives information on the non-trivial transitive group G acting on its natural set V. The most important component of this record is the list orbitalCombinations, whose elements give the sets of (the indices of) the G-orbitals whose union gives the edge-set of a distance-regular graph with vertex-set V. The component intersectionArrays gives the corresponding intersection arrays. The component degree is the degree of the permutation group G, rank is its (permutation) rank, and isPrimitive is true if G is primitive, and false otherwise.

    The techniques used in this function and definitions of the terms used above can be found in PS97.

    gap> m22:=PrimitiveGroup(22,1);;
    gap> syl:=SylowSubgroup(m22,11);;
    gap> part:=Set(Orbit(syl,1));;
    gap> l211:=Stabilizer(m22,part,OnSets);;
    gap> rt:=RightTransversal(m22,l211);;
    gap> m22big:=Action(m22,rt,OnRight);;
    gap> v:=VertexTransitiveDRGs(m22big);
    rec( degree := 672, rank := 6, isPrimitive := true, 
      orbitalCombinations := [ [ 2, 3, 4, 5, 6 ], [ 2, 4 ], [ 3, 5, 6 ], [ 3, 6 ] 
         ], 
      intersectionArrays := [ [ [ 0, 0, 671 ], [ 1, 670, 0 ] ], [ [ 0, 0, 495 ], 
              [ 1, 366, 128 ], [ 360, 135, 0 ] ], 
          [ [ 0, 0, 176 ], [ 1, 40, 135 ], [ 48, 128, 0 ] ], 
          [ [ 0, 0, 110 ], [ 1, 28, 81 ], [ 18, 80, 12 ], [ 90, 20, 0 ] ] ] )
    

    [Up] [Previous] [Next] [Index]

    grape manual
    October 2024