81:
71:
53:
22:
444:, the central vertex has high degree, and so the subgraph consisting only of that vertex would seem to have high average degree (if you measure degree in terms of the whole graph, not the subgraph). But it is not a dense subgraph. One possibility would be to replace "a high level of internal connectivity" with "many edges per vertex", or something like that. —
372:
Now, being 4-regular, it has a subgraph density of 2, and any proper subgraph has a lower density. But if we wanted to maximise internal connectivity, we would have chosen one of the "sides", e.g.
133:
483:
The example does not show the densest subgraph ... the induced graph $ G'=(V' = \{b,c,d,e,f,g,h\}, \choose{V'}{2} \cap E(G))$ has density $ d_{G'} = \frac{10}{7} = 1.428571 : -->
440:"Connectivity" here was intended in a less formal sense than the one you are using. But your suggested replacement, "average degree", would also be confusing. For instance, in a
414:
190:
The first sentence of the article currently reads: "In graph theory and computer science, a dense subgraph is a subgraph with a high level of internal connectivity."
315:
367:
341:
243:
220:
519:
283:
263:
127:
514:
103:
491:
94:
58:
33:
449:
495:
21:
39:
80:
176:
487:
429:
445:
441:
102:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
172:
86:
196:
Consider the following example of a 4-regular graph on 10 vertices that contains a 2-edge cut:
70:
52:
375:
169:? graph density is |E| / choose(|V|, 2), yet subgraph density here is defined as |E| / |V|.
466:
423:
288:
346:
320:
461:
The suggestion of "many edges per vertex" (or something like that) sounds much better.
225:
202:
268:
248:
508:
166:
99:
462:
419:
76:
193:
But the notion of connectivity here confused me when first reading it.
499:
470:
458:
I absolutely see, now, why my suggested replacement was also confusing.
453:
433:
180:
245:
be the edges of the 2-edge cut. Insert 3 parallel edges between
15:
378:
349:
323:
291:
271:
251:
228:
205:
98:, a collaborative effort to improve the coverage of
408:
361:
335:
309:
277:
257:
237:
214:
132:This article has not yet received a rating on the
165:should subgraph density be defined similarly to
317:, and connect these new vertices by a triangle
8:
19:
427:
47:
377:
348:
322:
290:
270:
250:
227:
204:
416:, which I believe is 3-edge connected.
49:
285:, subdivide them introducing vertices
520:Unknown-priority mathematics articles
7:
92:This article is within the scope of
38:It is of interest to the following
14:
112:Knowledge:WikiProject Mathematics
515:Start-Class mathematics articles
115:Template:WikiProject Mathematics
79:
69:
51:
20:
1:
471:14:49, 31 December 2022 (UTC)
454:07:58, 31 December 2022 (UTC)
434:07:31, 31 December 2022 (UTC)
426:) 08:21, Dec 31, 2022 (ECT)
106:and see a list of open tasks.
500:13:07, 12 August 2014 (UTC)
536:
409:{\displaystyle a,b,c,d,e}
186:First sentence confusing?
181:20:10, 12 July 2013 (UTC)
131:
64:
46:
134:project's priority scale
95:WikiProject Mathematics
410:
363:
337:
311:
279:
259:
239:
216:
28:This article is rated
484:1.4 = \frac{7}{5}$
411:
364:
338:
312:
310:{\displaystyle c,d,e}
280:
260:
240:
217:
376:
347:
321:
289:
269:
249:
226:
203:
118:mathematics articles
442:Star (graph theory)
362:{\displaystyle x,y}
343:. Similarly on the
336:{\displaystyle cde}
406:
359:
333:
307:
275:
255:
238:{\displaystyle by}
235:
215:{\displaystyle ax}
212:
87:Mathematics portal
34:content assessment
490:comment added by
479:Example incorrect
436:
278:{\displaystyle b}
258:{\displaystyle a}
148:
147:
144:
143:
140:
139:
527:
502:
415:
413:
412:
407:
368:
366:
365:
360:
342:
340:
339:
334:
316:
314:
313:
308:
284:
282:
281:
276:
264:
262:
261:
256:
244:
242:
241:
236:
221:
219:
218:
213:
162:
161:
157:
120:
119:
116:
113:
110:
89:
84:
83:
73:
66:
65:
55:
48:
31:
25:
24:
16:
535:
534:
530:
529:
528:
526:
525:
524:
505:
504:
485:
481:
374:
373:
345:
344:
319:
318:
287:
286:
267:
266:
247:
246:
224:
223:
201:
200:
188:
163:
159:
155:
153:
152:
117:
114:
111:
108:
107:
85:
78:
32:on Knowledge's
29:
12:
11:
5:
533:
531:
523:
522:
517:
507:
506:
492:134.34.225.175
480:
477:
476:
475:
474:
473:
459:
446:David Eppstein
432:comment added
405:
402:
399:
396:
393:
390:
387:
384:
381:
358:
355:
352:
332:
329:
326:
306:
303:
300:
297:
294:
274:
254:
234:
231:
211:
208:
187:
184:
151:
149:
146:
145:
142:
141:
138:
137:
130:
124:
123:
121:
104:the discussion
91:
90:
74:
62:
61:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
532:
521:
518:
516:
513:
512:
510:
503:
501:
497:
493:
489:
478:
472:
468:
464:
460:
457:
456:
455:
451:
447:
443:
439:
438:
437:
435:
431:
425:
421:
417:
403:
400:
397:
394:
391:
388:
385:
382:
379:
370:
356:
353:
350:
330:
327:
324:
304:
301:
298:
295:
292:
272:
252:
232:
229:
209:
206:
197:
194:
191:
185:
183:
182:
178:
174:
170:
168:
167:graph density
158:
150:
135:
129:
126:
125:
122:
105:
101:
97:
96:
88:
82:
77:
75:
72:
68:
67:
63:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
486:— Preceding
482:
428:— Preceding
418:
371:
198:
195:
192:
189:
171:
164:
93:
40:WikiProjects
109:Mathematics
100:mathematics
59:Mathematics
30:Start-class
509:Categories
488:unsigned
430:undated
369:side.
173:Mmuurr
154:": -->
36:scale.
463:Vuniu
420:Vuniu
496:talk
467:talk
450:talk
424:talk
265:and
222:and
199:Let
177:talk
156:edit
128:???
511::
498:)
469:)
452:)
179:)
494:(
465:(
448:(
422:(
404:e
401:,
398:d
395:,
392:c
389:,
386:b
383:,
380:a
357:y
354:,
351:x
331:e
328:d
325:c
305:e
302:,
299:d
296:,
293:c
273:b
253:a
233:y
230:b
210:x
207:a
175:(
160:]
136:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
