92:
80:
68:
55:
of the left-hand graph below is (3, 3, 3, 2, 2, 1) and its frequency partition is 6 = 3 + 2 + 1. This indicates that it has 3 vertices with some degree, 2 vertices with some other degree, and 1 vertex with a third degree. The degree sequence of the
60:
in the middle below is (3, 2, 2, 2, 2, 2, 1, 1, 1) and its frequency partition is 9 = 5 + 3 + 1. The degree sequence of the right-hand graph below is (3, 3, 3, 3, 3, 3, 2) and its frequency partition is 7 = 6 + 1.
510:, A survey of the theory of potentially p-graphic and forcibly p-graphic sequences, in: S. B. Rao edited., Combinatorics and Graph Theory Lecture Notes in Math., Vol. 885 (Springer, Berlin, 1981), 417-440
274:
79:
390:
91:
144:
Frequency partitions of various graph families are completely identified; frequency partitions of many families of graphs are not identified.
361:
Rao, Siddani
Bhaskara; Bhat-Nayak, Vasanti N.; Naik, Ranjan N. (1979), "Characterization of frequency partitions of Eulerian graphs",
536:
428:
67:
141:= 1 + 1 + 1 + ... + 1, there is at least one (connected) simple graph having this partition as its frequency partition.
296:
153:
44:
554:
419:
187:
48:
285:
102:
In general, there are many non-isomorphic graphs with a given frequency partition. A graph and its
426:(1977), "Frequency partitions: forcibly pancyclic and forcibly nonhamiltonian degree sequences",
532:
311:
The frequency partitions of the following families of graphs have not yet been characterized:
289:
489:
Bhat-Nayak, V. N. & Naik, R. N. (1985), "Frequency partitions of k-uniform hypergraphs",
239:
472:
437:
399:
103:
370:
375:
366:
320:
57:
52:
292:
350:, Lecture Notes in Mathematics, vol. 186, Berlin: Springer-Verlag, pp. 69–70
548:
456:
442:
404:
363:
Proceedings of the
Symposium on Graph Theory (Indian Statist. Inst., Calcutta, 1976)
524:
365:, ISI Lecture Notes, vol. 4, Macmillan of India, New Delhi, pp. 124–137,
40:
28:
17:
343:
32:
460:
315:
300:
507:
423:
280:
Frequency partition of trees, Hamiltonian graphs, tournaments and hypegraphs
476:
374:. Also in Lecture Notes in Mathematics, Combinatorics and Graph Theory,
236:(1979) showed that a partition of p with k parts, k ≤ integral part of
348:
The frequency partition of a graph. Recent Trends in Graph Theory
276:
is a frequency partition of a
Eulerian graph and conversely.
463:(1978), "Degree Frequencies in Digraphs and Tournaments",
85:
A bipartite graph with frequency partition 9 = 5 + 3 + 1.
284:
The frequency partitions of families of graphs such as
242:
106:
have the same frequency partition. For any partition
388:
Rao, T. M. (1974), "Frequency sequences in Graphs",
268:
73:A graph with frequency partition 6 = 3 + 2 + 1.
8:
97:A graph with frequency partition 7 = 6 + 1.
51:grouped by their degree. For example, the
529:Hypergraphs, Combinatorics of Finite sets
441:
403:
391:Journal of Combinatorial Theory, Series B
307:Unsolved problems in frequency partitions
258:
241:
335:
148:Frequency partitions of Eulerian graphs
63:
7:
378:, New York, Vol. 885 (1980), p 500.
25:
90:
78:
66:
255:
243:
1:
531:, Amsterdam: North-Holland,
443:10.1016/0012-365x(77)90049-8
405:10.1016/0095-8956(74)90042-2
303:. have been characterized.
571:
422:; Naik, Ranjan N. &
465:Journal of Graph Theory
269:{\displaystyle (p-1)/2}
188:graphic degree sequence
477:10.1002/jgt.3190020307
420:Bhat-Nayak, Vasanti N.
270:
31:, a discipline within
271:
210:'s are different and
429:Discrete Mathematics
240:
137:> 1, other than
206:) ) where degrees d
37:frequency partition
18:Frequency partition
290:Hamiltonian graphs
266:
299:and to k-uniform
190:is denoted as ((d
16:(Redirected from
562:
541:
518:External section
511:
505:
499:
498:
486:
480:
479:
453:
447:
446:
445:
415:
409:
408:
407:
385:
379:
373:
358:
352:
351:
340:
321:Bipartite graphs
275:
273:
272:
267:
262:
228: <
152:For a frequency
94:
82:
70:
21:
570:
569:
565:
564:
563:
561:
560:
559:
545:
544:
539:
523:
520:
515:
514:
506:
502:
488:
487:
483:
455:
454:
450:
418:
416:
412:
387:
386:
382:
376:Springer-Verlag
360:
359:
355:
342:
341:
337:
332:
326:
309:
293:directed graphs
282:
238:
237:
223:
216:
209:
205:
201:
197:
193:
181:
172:
165:
150:
132:
123:
116:
98:
95:
86:
83:
74:
71:
58:bipartite graph
53:degree sequence
23:
22:
15:
12:
11:
5:
568:
566:
558:
557:
547:
546:
543:
542:
537:
519:
516:
513:
512:
500:
491:Utilitas Math.
481:
471:(3): 241–249,
448:
410:
380:
353:
334:
333:
331:
328:
324:
323:
318:
308:
305:
281:
278:
265:
261:
257:
254:
251:
248:
245:
221:
214:
207:
203:
199:
195:
191:
182:of an integer
177:
170:
163:
149:
146:
133:of an integer
128:
121:
114:
100:
99:
96:
89:
87:
84:
77:
75:
72:
65:
24:
14:
13:
10:
9:
6:
4:
3:
2:
567:
556:
553:
552:
550:
540:
538:0-444-87489-5
534:
530:
526:
522:
521:
517:
509:
504:
501:
496:
492:
485:
482:
478:
474:
470:
466:
462:
458:
452:
449:
444:
439:
435:
431:
430:
425:
421:
414:
411:
406:
401:
397:
393:
392:
384:
381:
377:
372:
368:
364:
357:
354:
349:
345:
339:
336:
329:
327:
322:
319:
317:
314:
313:
312:
306:
304:
302:
298:
294:
291:
287:
279:
277:
263:
259:
252:
249:
246:
235:
232:. Bhat-Nayak
231:
227:
220:
213:
189:
185:
180:
176:
169:
162:
158:
155:
147:
145:
142:
140:
136:
131:
127:
120:
113:
109:
105:
93:
88:
81:
76:
69:
64:
62:
59:
54:
50:
46:
42:
38:
34:
30:
19:
555:Graph theory
528:
503:
494:
490:
484:
468:
464:
451:
433:
427:
413:
395:
389:
383:
362:
356:
347:
344:Chinn, P. Z.
338:
325:
310:
283:
233:
229:
225:
218:
211:
186:> 1, its
183:
178:
174:
167:
160:
156:
151:
143:
138:
134:
129:
125:
118:
111:
107:
101:
41:simple graph
39:of a graph (
36:
29:graph theory
26:
461:Reid, K. B.
457:Alspach, B.
316:Line graphs
301:hypergraphs
297:tournaments
33:mathematics
436:: 93–102,
424:Rao, S. B.
330:References
202:), ..., (d
104:complement
525:Berge, C.
508:S. B. Rao
398:: 19–21,
250:−
154:partition
45:partition
549:Category
527:(1989),
497:: 99–104
346:(1971),
173:+ ... +
124:+ ... +
49:vertices
371:0553937
47:of its
43:) is a
535:
459:&
369:
234:et al.
35:, the
286:trees
198:), (d
533:ISBN
295:and
224:for
194:),(d
473:doi
438:doi
400:doi
27:In
551::
495:28
493:,
467:,
434:20
432:,
396:17
394:,
367:MR
288:,
217:≥
166:+
159:=
117:+
110:=
475::
469:2
440::
417:*
402::
264:2
260:/
256:)
253:1
247:p
244:(
230:j
226:i
222:j
219:f
215:i
212:f
208:i
204:k
200:3
196:2
192:1
184:p
179:k
175:f
171:2
168:f
164:1
161:f
157:p
139:p
135:p
130:k
126:f
122:2
119:f
115:1
112:f
108:p
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.