63:
Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices,
353:
389:(or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product): it is a commutative and associative operation (for unlabelled graphs),
355:. Graph with all the edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation (for unlabelled graphs);
463:
500:
Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders".
374:
72:
between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.
36:
368:
417:
606:
392:
564:
403:
386:
380:
225:
409:
228:, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of
32:
502:
434:
318:
377:(or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation,
69:
529:
511:
229:
459:
362:
581:
573:
521:
138:
90:
65:
44:
541:
537:
108:
84:
40:
80:
Advanced operations create a new graph from an initial one by a complex change, such as:
358:
132:
114:
600:
555:
559:
483:
126:
24:
20:
423:
parallel graph composition: it is a commutative operation (for unlabelled graphs),
429:
source graph composition: it is a commutative operation (for unlabelled graphs);
144:
102:
120:
96:
586:
383:: it is a commutative and associative operation (for unlabelled graphs),
371:: it is a commutative and associative operation (for unlabelled graphs),
577:
533:
516:
525:
406:: it is an associative operation (for unlabelled but rooted graphs),
55:
Unary operations create a new graph from a single initial graph.
232:
in mathematics) the union of two graphs is defined as the graph
156:
Binary operations create a new graph from two initial graphs
426:
series graph composition: it is a non-commutative operation,
224:. There are two definitions. In the most common one, the
458:. Graduate Texts in Mathematics. Springer. p. 29.
16:
Procedures for constructing new graphs in graph theory
321:
347:
8:
585:
515:
339:
326:
320:
479:
477:
475:
562:(1970). "On the corona of two graphs".
446:
400:graph product based on other products:
454:Bondy, J. A.; Murty, U. S. R. (2008).
39:from initial ones. They include both
7:
490:. Reading, MA: Addison-Wesley, 1994.
412:: it is a non-commutative operation;
332:
14:
418:series–parallel graph composition
348:{\displaystyle G_{1}\nabla G_{2}}
1:
375:lexicographic graph product
623:
565:Aequationes Mathematicae
226:disjoint union of graphs
47:(two input) operations.
369:cartesian graph product
349:
503:Annals of Mathematics
393:zig-zag graph product
350:
59:Elementary operations
410:corona graph product
404:rooted graph product
387:tensor graph product
381:strong graph product
365:of the vertex sets:
319:
267:graph intersection:
76:Advanced operations
70:graph edit distance
578:10.1007/bf01844162
435:Hajós construction
345:
35:which produce new
465:978-1-84628-969-9
363:cartesian product
152:Binary operations
614:
607:Graph operations
592:
591:
589:
552:
546:
545:
519:
497:
491:
481:
470:
469:
451:
354:
352:
351:
346:
344:
343:
331:
330:
311:
263:
223:
203:
179:
91:complement graph
66:edge contraction
51:Unary operations
43:(one input) and
29:graph operations
622:
621:
617:
616:
615:
613:
612:
611:
597:
596:
595:
554:
553:
549:
526:10.2307/3062153
499:
498:
494:
482:
473:
466:
453:
452:
448:
444:
335:
322:
317:
316:
309:
302:
295:
288:
281:
274:
268:
261:
254:
247:
240:
233:
222:
215:
209:
201:
194:
187:
181:
177:
170:
163:
157:
154:
109:graph rewriting
85:transpose graph
78:
61:
53:
17:
12:
11:
5:
620:
618:
610:
609:
599:
598:
594:
593:
556:Frucht, Robert
547:
510:(1): 157–187.
492:
471:
464:
445:
443:
440:
439:
438:
432:
431:
430:
427:
424:
415:
414:
413:
407:
398:
397:
396:
390:
384:
378:
372:
359:graph products
356:
342:
338:
334:
329:
325:
313:
307:
300:
293:
286:
279:
272:
265:
259:
252:
245:
238:
220:
213:
199:
192:
185:
175:
168:
161:
153:
150:
149:
148:
142:
136:
133:quotient graph
130:
124:
118:
115:power of graph
112:
106:
100:
94:
88:
77:
74:
60:
57:
52:
49:
15:
13:
10:
9:
6:
4:
3:
2:
619:
608:
605:
604:
602:
588:
587:2027.42/44326
583:
579:
575:
571:
567:
566:
561:
560:Harary, Frank
557:
551:
548:
543:
539:
535:
531:
527:
523:
518:
513:
509:
505:
504:
496:
493:
489:
485:
480:
478:
476:
472:
467:
461:
457:
450:
447:
441:
436:
433:
428:
425:
422:
421:
419:
416:
411:
408:
405:
402:
401:
399:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
366:
364:
361:based on the
360:
357:
340:
336:
327:
323:
314:
306:
299:
292:
285:
278:
271:
266:
258:
251:
244:
237:
231:
227:
219:
212:
208:graph union:
207:
206:
205:
198:
191:
184:
174:
167:
160:
151:
146:
143:
140:
139:Y-Δ transform
137:
134:
131:
128:
125:
122:
119:
116:
113:
110:
107:
104:
101:
98:
95:
92:
89:
86:
83:
82:
81:
75:
73:
71:
67:
58:
56:
50:
48:
46:
42:
38:
34:
30:
26:
22:
569:
563:
550:
517:math/0406038
507:
501:
495:
488:Graph Theory
487:
456:Graph Theory
455:
449:
315:graph join:
304:
297:
290:
283:
276:
269:
256:
249:
242:
235:
217:
210:
196:
189:
182:
172:
165:
158:
155:
127:medial graph
79:
62:
54:
28:
25:graph theory
21:mathematical
18:
572:: 322–324.
204:, such as:
145:Mycielskian
103:graph minor
68:, etc. The
121:dual graph
97:line graph
33:operations
484:Harary, F
333:∇
23:field of
601:Category
542:1888797
534:3062153
19:In the
540:
532:
462:
45:binary
37:graphs
530:JSTOR
512:arXiv
442:Notes
230:union
41:unary
460:ISBN
180:and
31:are
582:hdl
574:doi
522:doi
508:155
282:= (
188:= (
164:= (
603::
580:.
568:.
558:;
538:MR
536:.
528:.
520:.
506:.
486:.
474:^
420::
303:∩
296:,
289:∩
275:∩
255:∪
248:,
241:∪
216:∪
195:,
171:,
27:,
590:.
584::
576::
570:4
544:.
524::
514::
468:.
437:.
395:;
341:2
337:G
328:1
324:G
312:;
310:)
308:2
305:E
301:1
298:E
294:2
291:V
287:1
284:V
280:2
277:G
273:1
270:G
264:.
262:)
260:2
257:E
253:1
250:E
246:2
243:V
239:1
236:V
234:(
221:2
218:G
214:1
211:G
202:)
200:2
197:E
193:2
190:V
186:2
183:G
178:)
176:1
173:E
169:1
166:V
162:1
159:G
147:.
141:;
135:;
129:;
123:;
117:;
111:;
105:;
99:;
93:;
87:;
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.