- InducedSubgraph
- DistanceSetInduced
- DistanceGraph
- ComplementGraph
- PointGraph
- EdgeGraph
- SwitchedGraph
- UnderlyingGraph
- QuotientGraph
- BipartiteDouble
- GeodesicsGraph
- CollapsedIndependentOrbitsGraph
- CollapsedCompleteOrbitsGraph
- NewGroupGraph

This chapter describes functions to construct new graphs from old ones.

`InducedSubgraph( `

`, `

` )`

`InducedSubgraph( `

`, `

`, `

` )`

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

`DistanceSetInduced( `

`, `

`, `

` )`

`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 ] ] )

`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 ] ]

`ComplementGraph( `

` )`

`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

`PointGraph( `

` )`

`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

`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
|*e*∩*f*|=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 ] ]

`SwitchedGraph( `

`, `

` )`

`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 ] ]

`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 )

`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 *x* ∈ *X*,
*y* ∈ *Y*. 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

`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

`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 ] ]

`CollapsedIndependentOrbitsGraph( `

`, `

` )`

`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 *x*∪*y* 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 ] ] )

`CollapsedCompleteOrbitsGraph( `

`, `

` )`

`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 *x* ≠ *y* and the subgraph of
`gamma` induced on *x*∪*y* 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 )

`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

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

grape manual

June 2018