Induced Subgraph in Gap program

Question

I'm stuck with a function in Gap. I want to construct an induced subgraph but when I remove a vertex, example 3 in V=(1,2,3,4,5), Gap numbers the remaining vertices from 1-4. Can I somehow keep the vertex number as they were before? I use the trivial group when constructing graph with EdgeOrbitsGraph. There is a third parameter in the function but I haven't learned about groups yet so I don't know how to use it. Thank you

Example

gap> LoadPackage("grape");
─────────────────────────────────────────────────────────────────────────────
Loading  GRAPE 4.6.1 (GRaph Algorithms using PErmutation groups)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/
─────────────────────────────────────────────────────────────────────────────
true
gap> T:=SymmetricGroup(0);
Group(())
gap> L:=[[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]];
[ [ 1, 2 ], [ 2, 1 ], [ 1, 3 ], [ 3, 1 ], [ 2, 3 ], [ 3, 2 ] ]
gap> G:=EdgeOrbitsGraph(T, L, 3); 
rec( adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ], group := Group(()), 
  isGraph := true, order := 3, representatives := [ 1, 2, 3 ], 
  schreierVector := [ -1, -2, -3 ] )
gap> V1:=[1,3]; 
[ 1, 3 ]
gap> H:=InducedSubgraph(G, V1); 
rec( adjacencies := [ [ 2 ], [ 1 ] ], group := Group(()), isGraph := true, 
  names := [ 1, 3 ], order := 2, representatives := [ 1, 2 ], 
  schreierVector := [ -1, -2 ] )

Answer 1

As Alexander Konovalov says in his comments this is a documented feature of the function InducedSubgraph. In fact, the vertex set of every graph in Grape is a range, for instance [ 1, 2, 3 ] and [ 1, 2 ] in your examples G and H. The original vertex name/number can be found using VertexName(H, v), where H is the induced subgraph and v is a number in the vertex set, so VertexName(H, 2) in your example will return 3.

There are several reasons that graphs are implemented this way in Grape. Many of the algorithms in Grape (and graph algorithms in general) use the adjacencies component of the graph object in some way or other. For example,

adjacencies := [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ]

in your graph G. The vertices adjacent to vertex 1 are adjacencies[1] = [ 2, 3 ].

Suppose you have a graph with 1000000 vertices, and you want the induced subgraph with vertices 999999 and 1000000. If these vertices are not renamed, then the list of adjacencies has length 1000000 and uses as much memory as the adjacencies of a 1 million vertex graph would. Even worse, many of the algorithms in Grape sequentially inspect the entries of the list of adjacencies. So, instead of inspecting two entries in our example, we have to inspect 1000000, even though only two of them even have a value. This results in more complicated and less efficient code.

This could also be resolved by making the correspondence between the indices of adjacencies and the vertices in the graph different (i.e. adjacencies[i] wouldn't any longer be those vertices adjacent to the vertex i). But again this would make the code more complicated.