[GAP Forum] Grape UndirectedEdges Question

[Leonard Soicher]

Dear Bill, Dear GAP Forum,

Further to Robert's answer, given a GRAPE graph  gamma  and a list
V of distinct vertices of  gamma,  with  V  invariant under a subgroup  G
of the automorphism group of  gamma,  the function call

InducedSubgraph( gamma, V, G )

returns the subgraph of gamma induced on the vertex list V,
with the image of G acting on V being the group associated with the
induced subgraph. If the parameter  G  is omitted then the associated
group is trivial. Vertex  i  in the induced subgraph corresponds to the
vertex V[i] of gamma  (so the order of elements in V does matter),
and the name of vertex  i  in the induced subgraph is equal
to the name of vertex V[i] in gamma.

I hope this and the GRAPE documentation are helpful.

Best wishes,
Leonard


________________________________________
From: Bailey, Robert F. <rbailey at grenfell.mun.ca>
Sent: 08 December 2021 00:54
To: Butske, Bill
Cc: forum at gap-system.org
Subject: Re: [GAP Forum] Grape UndirectedEdges Question

Dear Bill,

GRAPE always defaults to labelling the vertices of a n-vertex graph as [1..n].  So when you construct an induced subgraph on some k-subset of in this way, the new graph will be on vertex set [1..k].

However, when you define your subgraph "gamma_1_2_6", the original vertex names are preserved, in the ".names" component of the graph record:

gap> gamma_1_2_6;
rec( adjacencies := [ [ 2 ], [ 1, 3 ], [ 2 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 6 ],
  order := 3, representatives := [ 1, 2, 3 ], schreierVector := [ -1, -2, -3 ] )

So it *is* possible to extract the information you need from this:

gap> e:= UndirectedEdges(gamma_1_2_6);
[ [ 1, 2 ], [ 2, 3 ] ]
gap> List(e, x-> List(x, y->gamma_1_2_6.names[y]) );
[ [ 1, 2 ], [ 2, 6 ] ]

I hope this helps!

Best wishes,
Robert.

==============================
Dr. Robert Bailey
Associate Professor, Mathematics
Chair, General Science program
School of Science and the Environment
Grenfell Campus
Memorial University of Newfoundland
Corner Brook, NL A2H 6P9, Canada

Office: AS 3022
Phone: +1 (709) 637-6293
Web: http://www2.grenfell.mun.ca/rbailey/

-----Original Message-----
From: Butske, Bill <butske at rose-hulman.edu>
Sent: 07 December 2021 21:01
To: forum at gap-system.org
Subject: [GAP Forum] Grape UndirectedEdges Question

Dear All,

I'm having a bit of trouble (at least in my mind) with GRAPE.

I'm interested in subgraphs of the following graph and its associated symmetry group which I define through the adjacency matrix as follows:

gap>A:=[ [ 0, 1, 1, 1, 1, 0 ],
           [ 1, 0, 1, 0, 1, 1 ],
           [ 1, 1, 0, 1, 0, 1 ],
           [ 1, 0, 1, 0, 1, 1 ],
           [ 1, 1, 0, 1, 0, 1,],

           [ 0, 1, 1, 1, 1, 0 ] ];;

gap>G:=Group((2,3,4,5),(1,2,6,4));:

gap>LoadPackage("grape");;

gap>gamma:=Graph(G, [1..6], OnPoints, function(x,y) return A[x][y]=1; end, true );;

gap> UndirectedEdges(gamma);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ],
  [ 3, 6 ], [ 4, 5 ], [ 4, 6 ], [ 5, 6 ] ]

So far so good.  Then I define the induced subgraph determined by the vertices 1,2,6

gap>gamma_1_2_6:=InducedSubgraph(gamma,[1,2,6]);;

This should, in my mind anyway, give me the subgraph with the edges [1,2] and [2,6].  However, when I check this with the UndirectedEdges command I get:

gap> UndirectedEdges(InducedSubgraph(gamma,[1,2,6]));
[ [ 1, 2 ], [ 2, 3 ] ]

This bothers me because 3 isn't a specified vertex, furthermore the UndirectedEdges command appears to be order dependent?

gap> UndirectedEdges(InducedSubgraph(gamma,[1,6,2]));
[ [ 1, 3 ], [ 2, 3 ] ]

My expectation is that either version of the command should return [[1,2],[2,6]] and I am very much confused as to why this isn't case.

Any insights are appreciated and thanks in advance,
Bill Butske

_______________________________________________
Forum mailing list
Forum at gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum

_______________________________________________
Forum mailing list
Forum at gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum