6 Functions to construct new graphs from old

This function returns the subgraph of gamma induced on the vertex list V (which must not contain repeated elements). If the optional third parameter G is given, then it is assumed that G fixes V setwise, and is a group of automorphisms of the induced subgraph when restricted to V. In that case, the image of G acting on V is the group associated with the induced subgraph. If no such G is given then the associated group is trivial. The name of vertex i in the induced subgraph is equal to the name of vertex V[i] in gamma.

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

6.2 DistanceSetInduced

Let V be a vertex or a nonempty list of vertices of gamma. This function returns the subgraph of gamma induced on the set of vertices w of gamma such that d(V,w) is in distances (a list or singleton distance).

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.

See also Distance and DistanceSet.

gap> DistanceSetInduced( JohnsonGraph(4,2), [0,1], [1] );
rec(
  isGraph := true,
  order := 5,
  group := Group( [ (2,3)(4,5), (2,5)(3,4) ] ),
  schreierVector := [ -1, -2, 1, 2, 2 ],
  adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4 ] ],
  representatives := [ 1, 2 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] )

6.3 DistanceGraph

This function returns the graph delta, with the same vertex-set (and vertex-names) as gamma, such that [x,y] is an edge of delta if and only if d(x,y) (in gamma) is in distances (a list or singleton distance).

gap> DistanceGraph( JohnsonGraph(4,2), [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 := [ [ 6 ] ],
  representatives := [ 1 ],
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ],
  isSimple := true )
gap> ConnectedComponents(last);
[ [ 1, 6 ], [ 2, 5 ], [ 3, 4 ] ]

6.4 ComplementGraph

This function returns the complement of the graph gamma. The optional boolean parameter comploops determines whether or not loops/nonloops are complemented (default: false (loops/nonloops are not complemented)). The returned graph will have the same vertex-names as gamma.

gap> ComplementGraph( NullGraph(SymmetricGroup(3)) );
rec(
  isGraph := true,
  order := 3,
  group := SymmetricGroup( [ 1 .. 3 ] ),
  schreierVector := [ -1, 1, 1 ],
  adjacencies := [ [ 2, 3 ] ],
  representatives := [ 1 ],
  isSimple := true )
gap> IsLoopy(last);
false
gap> IsLoopy(ComplementGraph(NullGraph(SymmetricGroup(3)),true));
true

6.5 PointGraph

Assuming that gamma is simple, connected, and bipartite, this function returns the induced subgraph on the connected component of DistanceGraph(gamma,2) containing the vertex v (default: v=1).

Thus, if gamma is the incidence graph of a connected geometry of rank 2, and v represents a point, then the point graph of the geometry is returned.

gap> BipartiteDouble( CompleteGraph(SymmetricGroup(4)) );;
gap> PointGraph(last);
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,2), (1,2,3,4) ] ),
  schreierVector := [ -1, 1, 2, 2 ],
  adjacencies := [ [ 2, 3, 4 ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ 1, "+" ], [ 2, "+" ], [ 3, "+" ], [ 4, "+" ] ] )
gap> IsCompleteGraph(last);
true

6.6 EdgeGraph

This function return a graph isomorphic to the the edge graph (also called the line graph) of the simple graph gamma.

This edge graph delta has the unordered edges of gamma as vertices, and e is joined to f in delta precisely when |ecapf|=1. The name of the vertex of the returned graph corresponding to the unordered edge [v,w] of gamma (with v< w) is [VertexName(gamma,v),VertexName(gamma,w)].

gap> EdgeGraph( CompleteGraph(SymmetricGroup(5)) );
rec(
  isGraph := true,
  order := 10,
  group := Group( [ ( 1, 5, 8,10, 4)( 2, 6, 9, 3, 7), ( 2, 5)( 3, 6)( 4, 7)
     ] ),
  schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ],
  adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
      [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ] )
gap> GlobalParameters(last);
[ [ 0, 0, 6 ], [ 1, 3, 2 ], [ 4, 2, 0 ] ]

6.7 SwitchedGraph

This function returns the switched graph delta of the graph gamma, switched with respect to the vertex list (or singleton vertex) V.

The returned graph delta has vertex-set (and vertex-names) the same as gamma. If vertices x,y of delta are both in V or both not in V, then [x,y] is an edge of delta if and only if [x,y] is an edge of gamma; otherwise [x,y] is an edge of delta if and only if [x,y] is not an edge of gamma. If the optional third argument H is given, then it is assumed to be a subgroup of Aut(gamma) stabilizing V setwise.

gap> J:=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> S:=SwitchedGraph(J,[1,6]);
rec(
  isGraph := true,
  order := 6,
  group := Group( () ),
  schreierVector := [ -1, -2, -3, -4, -5, -6 ],
  adjacencies := [ [  ], [ 3, 4 ], [ 2, 5 ], [ 2, 5 ], [ 3, 4 ], [  ] ],
  representatives := [ 1, 2, 3, 4, 5, 6 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ] )
gap> ConnectedComponents(S);
[ [ 1 ], [ 2, 3, 4, 5 ], [ 6 ] ]

6.8 UnderlyingGraph

This function returns the underlying graph delta of gamma. The graph delta has the same vertex-set (and vertex-names) as gamma, and has an edge [x,y] precisely when gamma has an edge [x,y] or an edge [y,x]. This function also sets the isSimple components of gamma and delta.

gap> gamma := EdgeOrbitsGraph( Group((1,2,3,4)), [1,2] );
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,2,3,4) ] ),
  schreierVector := [ -1, 1, 1, 1 ],
  adjacencies := [ [ 2 ] ],
  representatives := [ 1 ],
  isSimple := false )
gap> UnderlyingGraph(gamma);
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,2,3,4) ] ),
  schreierVector := [ -1, 1, 1, 1 ],
  adjacencies := [ [ 2, 4 ] ],
  representatives := [ 1 ],
  isSimple := true )

6.9 QuotientGraph

Let S be the smallest gamma.group-invariant equivalence relation on the vertices of gamma, such that S contains the relation R (which should be a list of ordered pairs (length 2 lists) of vertices of gamma). Then this function returns a graph isomorphic to the quotient delta of the graph gamma, defined as follows. The vertices of delta are the equivalence classes of S, and [X,Y] is an edge of delta if and only if [x,y] is an edge of gamma for some xinX, yinY. The name of a vertex v in the returned graph is a list (not necessarily ordered) of the vertex-names of gamma for the vertices in the equivalence class corresponding to v.

gap> gamma := JohnsonGraph(4,2);;
gap> QuotientGraph( gamma, [[1,6]] );
rec(
  isGraph := true,
  order := 3,
  group := Group( [ (1,3), (2,3) ] ),
  schreierVector := [ -1, 2, 1 ],
  adjacencies := [ [ 2, 3 ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
      [ [ 1, 4 ], [ 2, 3 ] ] ] )
gap> IsCompleteGraph(last);
true

6.10 BipartiteDouble

This function returns the bipartite double of the graph gamma, as defined in BCN89.

gap> gamma := JohnsonGraph(4,2);;
gap> IsBipartite(gamma);
false
gap> delta := BipartiteDouble(gamma);
rec(
  isGraph := true,
  order := 12,
  group := Group( [ ( 1, 4, 6, 3)( 2, 5)( 7,10,12, 9)( 8,11),
      ( 2, 4)( 3, 5)( 8,10)( 9,11), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)
        ( 6,12) ] ),
  schreierVector := [ -1, 2, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3 ],
  adjacencies := [ [ 8, 9, 10, 11 ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
      [ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
      [ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
      [ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
gap> IsBipartite(delta);
true

6.11 GeodesicsGraph

This function returns the the graph induced on the set of geodesics in gamma between the vertices x and y, but including neither x nor y. This function is only for a simple graph gamma.

gap> GeodesicsGraph( JohnsonGraph(4,2), 1, 6 );
rec(
  isGraph := true,
  order := 4,
  group := Group( [ (1,3)(2,4), (1,4)(2,3), (2,3) ] ),
  schreierVector := [ -1, 2, 1, 2 ],
  adjacencies := [ [ 2, 3 ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] )
gap> GlobalParameters(last);
[ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ]

6.12 CollapsedIndependentOrbitsGraph

Given a subgroup G of the automorphism group of the simple graph gamma, this function returns a graph isomorphic to delta, defined as follows. The vertices of delta are those G-orbits of the vertices of gamma that are independent sets in gamma, and x is joined to y in delta if and only if xcupy is not an independent set in gamma. The name of a vertex v in the returned graph is a list (not necessarily ordered) of the vertex-names of gamma for the vertices in the G-orbit corresponding to v.

If the optional parameter N is given, then it is assumed to be a subgroup of Aut(gamma) preserving the set of G-orbits of the vertices of gamma (for example, the normalizer in gamma.group of G). This information can make the function more efficient.

gap> G := Group( (1,2) );;
gap> gamma := NullGraph( SymmetricGroup(3) );;
gap> CollapsedIndependentOrbitsGraph( G, gamma );
rec(
  isGraph := true,
  order := 2,
  group := Group( [ () ] ),
  schreierVector := [ -1, -2 ],
  adjacencies := [ [  ], [  ] ],
  representatives := [ 1, 2 ],
  isSimple := true,
  names := [ [ 1, 2 ], [ 3 ] ] )
gap> gamma := CompleteGraph( SymmetricGroup(3) );;
gap> CollapsedIndependentOrbitsGraph( G, gamma );
rec(
  isGraph := true,
  order := 1,
  group := Group( [ () ] ),
  schreierVector := [ -1 ],
  adjacencies := [ [  ] ],
  representatives := [ 1 ],
  isSimple := true,
  names := [ [ 3 ] ] )

6.13 CollapsedCompleteOrbitsGraph

Given a subgroup G of the automorphism group of the simple graph gamma, this function returns a graph isomorphic to delta, defined as follows. The vertices of delta are those G-orbits of the vertices of gamma on which complete subgraphs are induced in gamma, and x is joined to y in delta if and only if xnot=y and the subgraph of gamma induced on xcupy is a complete graph. The name of a vertex v in the returned graph is a list (not necessarily ordered) of the vertex-names of gamma for the vertices in the G-orbit corresponding to v.

If the optional parameter N is given, then it is assumed to be a subgroup of Aut(gamma) preserving the set of G-orbits of the vertices of gamma (for example, the normalizer in gamma.group of G). This information can make the function more efficient.

gap> G := Group( (1,2) );;
gap> gamma := NullGraph( SymmetricGroup(3) );;
gap> CollapsedCompleteOrbitsGraph( G, gamma );
rec(
  isGraph := true,
  order := 1,
  group := Group( [ () ] ),
  schreierVector := [ -1 ],
  adjacencies := [ [  ] ],
  representatives := [ 1 ],
  names := [ [ 3 ] ],
  isSimple := true )
gap> gamma := CompleteGraph( SymmetricGroup(3) );;
gap> CollapsedCompleteOrbitsGraph( G, gamma );
rec(
  isGraph := true,
  order := 2,
  group := Group( [ () ] ),
  schreierVector := [ -1, -2 ],
  adjacencies := [ [ 2 ], [ 1 ] ],
  representatives := [ 1, 2 ],
  names := [ [ 1, 2 ], [ 3 ] ],
  isSimple := true )

6.14 NewGroupGraph

This function returns a copy delta of gamma, except that the group associated with delta is G, which is assumed to be a subgroup of Aut(delta).

Note that the results of some functions of a graph depend on the group associated with that graph (which must always be a subgroup of the automorphism group of the graph).

gap> gamma := JohnsonGraph(4,2);;
gap> aut := AutGroupGraph(gamma);
Group([ (3,4), (2,3)(4,5), (1,2)(5,6) ])
gap> Size(gamma.group);
24
gap> Size(aut);
48
gap> delta := NewGroupGraph( aut, gamma );;
gap> Size(delta.group);
48
gap> IsIsomorphicGraph( gamma, delta );
true

6.15 GraphImage

This function returns the image of the graph gamma of order n, under the permutation g of the vertex set {1,...,n} of gamma.

gap> J:=JohnsonGraph(4,2);                    
rec( adjacencies := [ [ 2, 3, 4, 5 ] ], group := Group([ (1,4,6,3)(2,5), (2,4)
  (3,5) ]), isGraph := true, isSimple := true, 
  names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ], 
  order := 6, representatives := [ 1 ], 
  schreierVector := [ -1, 2, 1, 1, 1, 1 ] )
gap> JIm:=GraphImage(J,(1,2,3,4,5));
rec( adjacencies := [ [ 2, 4, 5, 6 ] ], group := Group([ (1,3)(2,5,6,4), (1,4)
  (3,5) ]), isGraph := true, isSimple := true, 
  names := [ [ 2, 4 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ] ], 
  order := 6, representatives := [ 1 ], 
  schreierVector := [ -1, 1, 1, 2, 2, 1 ] )
gap> IsIsomorphicGraph(J,JIm);
true

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