[GAP Forum] Grape UndirectedEdges Question

[Bailey, Robert F.]

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