File: constr.tex

package info (click to toggle)
gap-grape 4.8.1%2Bds-3
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 708 kB
  • sloc: sh: 16; makefile: 12
file content (473 lines) | stat: -rw-r--r-- 15,842 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A  constr.tex               GRAPE documentation              Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\nauty{\it nauty}
\def\Aut{{\rm Aut}\,}

\Chapter{Functions to construct new graphs from old}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{InducedSubgraph}

\>InducedSubgraph( <gamma>, <V> )
\>InducedSubgraph( <gamma>, <V>, <G> )

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

\beginexample
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 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceSetInduced}

\>DistanceSetInduced( <gamma>, <distances>, <V> )
\>DistanceSetInduced( <gamma>, <distances>, <V>, <G> )

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". 

\beginexample
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 ] ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DistanceGraph}

\>DistanceGraph( <gamma>, <distances> )

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

\beginexample
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 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{ComplementGraph}

\>ComplementGraph( <gamma> )
\>ComplementGraph( <gamma>, <comploops> )

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

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{PointGraph}

\>PointGraph( <gamma> )
\>PointGraph( <gamma>, <v> )

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.

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{EdgeGraph}

\>EdgeGraph( <gamma> )

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\cap 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>)]'.

\beginexample
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 ] ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SwitchedGraph}

\>SwitchedGraph( <gamma>, <V> ) 
\>SwitchedGraph( <gamma>, <V>, <H> ) 

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.

\beginexample
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 ] ]
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{UnderlyingGraph}

\>UnderlyingGraph( <gamma> )

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

\beginexample
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 )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{QuotientGraph}

\>QuotientGraph( <gamma>, <R> )

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\in X$,
$y\in 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$.

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{BipartiteDouble}

\>BipartiteDouble( <gamma> )

This function  returns the  bipartite  double  of the graph  <gamma>,  as
defined in \cite{BCN89}.

\beginexample
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
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{GeodesicsGraph}

\>GeodesicsGraph( <gamma>, <x>, <y> )

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

\beginexample
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 ] ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedIndependentOrbitsGraph}

\>CollapsedIndependentOrbitsGraph( <G>, <gamma> )
\>CollapsedIndependentOrbitsGraph( <G>, <gamma>, <N> )

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\cup 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.

\beginexample
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 ] ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CollapsedCompleteOrbitsGraph}

\>CollapsedCompleteOrbitsGraph( <G>, <gamma> )
\>CollapsedCompleteOrbitsGraph( <G>, <gamma>, <N> )

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\not=y$ and the subgraph of
<gamma> induced on $x\cup 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.

\beginexample
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 )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{NewGroupGraph}

\>NewGroupGraph( <G>, <gamma> )

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

\beginexample
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
\endexample