20:
50:, and is constructed by making the vertex set of the result be the disjoint union of the vertex sets of the given graphs, and by making the edge set of the result be the disjoint union of the edge sets of the given graphs. Any disjoint union of two or more nonempty graphs is necessarily
160:
134:
108:
88:
213:
321:
279:
255:
341:
43:
307:
51:
223:
are the graphs that can be constructed from single-vertex graphs by a combination of disjoint union and
381:
170:
Certain special classes of graphs may be represented using disjoint union operations. In particular:
139:
245:
175:
362:
311:
8:
179:
113:
93:
73:
354:
317:
275:
251:
350:
293:
224:
358:
209:
296:, Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
190:
47:
28:
375:
336:
197:
186:
24:
339:; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs",
272:
Discrete
Mathematics: An Introduction to Concepts, Methods, and Applications
35:
201:
250:, Discrete Mathematics and Its Applications, CRC Press, p. 515,
67:
220:
316:, Dover Books on Mathematics, Courier Corporation, p. 201,
335:
19:
208:
More generally, every graph is the disjoint union of
142:
116:
96:
76:
247:Handbook of Discrete and Combinatorial Mathematics
154:
128:
102:
82:
373:
16:Combining the vertex and edge sets of two graphs
46:to form a larger graph. It is analogous to the
305:
42:is an operation that combines two or more
269:
165:
18:
374:
62:The disjoint union is also called the
243:
66:, and may be represented either by a
13:
14:
393:
38:, a branch of mathematics, the
329:
313:A First Course in Graph Theory
299:
287:
263:
237:
162:denotes their disjoint union.
1:
270:Grossman, Jerrold W. (1990),
230:
355:10.1016/0166-218X(81)90013-5
342:Discrete Applied Mathematics
7:
200:are the disjoint unions of
189:are the disjoint unions of
178:are the disjoint unions of
70:or a circled plus sign: If
57:
10:
398:
274:, Macmillan, p. 627,
244:Rosen, Kenneth H. (1999),
155:{\displaystyle G\oplus H}
40:disjoint union of graphs
27:, the disjoint union of
156:
130:
104:
84:
48:disjoint union of sets
31:
166:Related graph classes
157:
131:
110:are two graphs, then
105:
85:
22:
214:connected components
140:
114:
94:
74:
129:{\displaystyle G+H}
152:
126:
100:
80:
32:
306:Chartrand, Gary;
103:{\displaystyle H}
83:{\displaystyle G}
389:
382:Graph operations
366:
365:
333:
327:
326:
303:
297:
291:
285:
284:
267:
261:
260:
241:
210:connected graphs
198:2-regular graphs
161:
159:
158:
153:
135:
133:
132:
127:
109:
107:
106:
101:
89:
87:
86:
81:
397:
396:
392:
391:
390:
388:
387:
386:
372:
371:
370:
369:
334:
330:
324:
304:
300:
292:
288:
282:
268:
264:
258:
242:
238:
233:
191:complete graphs
168:
141:
138:
137:
115:
112:
111:
95:
92:
91:
75:
72:
71:
60:
29:complete graphs
17:
12:
11:
5:
395:
385:
384:
368:
367:
349:(3): 163–174,
337:Corneil, D. G.
328:
322:
298:
294:Cluster graphs
286:
280:
262:
256:
235:
234:
232:
229:
206:
205:
194:
187:cluster graphs
183:
167:
164:
151:
148:
145:
125:
122:
119:
99:
79:
59:
56:
15:
9:
6:
4:
3:
2:
394:
383:
380:
379:
377:
364:
360:
356:
352:
348:
344:
343:
338:
332:
325:
323:9780486297309
319:
315:
314:
309:
302:
295:
290:
283:
281:9780023483318
277:
273:
266:
259:
257:9780849301490
253:
249:
248:
240:
236:
228:
226:
222:
217:
215:
211:
203:
199:
195:
192:
188:
184:
181:
177:
173:
172:
171:
163:
149:
146:
143:
123:
120:
117:
97:
77:
69:
65:
55:
53:
49:
45:
41:
37:
30:
26:
25:cluster graph
21:
346:
340:
331:
312:
301:
289:
271:
265:
246:
239:
227:operations.
218:
207:
202:cycle graphs
169:
63:
61:
52:disconnected
39:
36:graph theory
33:
308:Zhang, Ping
231:References
225:complement
147:⊕
68:plus sign
64:graph sum
376:Category
310:(2013),
221:cographs
58:Notation
363:0619603
176:forests
361:
320:
278:
254:
212:, its
44:graphs
180:trees
318:ISBN
276:ISBN
252:ISBN
219:The
196:The
185:The
174:The
90:and
351:doi
136:or
34:In
378::
359:MR
357:,
345:,
216:.
54:.
23:A
353::
347:3
204:.
193:.
182:.
150:H
144:G
124:H
121:+
118:G
98:H
78:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.