Graphical Partition

A partition {a_1,...,a_n}" src="https://mathworld.wolfram.com/images/equations/GraphicalPartition/Inline1.svg" style="height:22px; width:88px" /> is called graphical if there exists a graph  having degree sequence {a_1,...,a_n}" src="https://mathworld.wolfram.com/images/equations/GraphicalPartition/Inline3.svg" style="height:22px; width:88px" />. The number of graphical partitions of length  is equal to the number of -node graphs that have no isolated points.

The numbers of distinct graphical partitions corresponding to graphs on , 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148, ... (OEIS A095268).

A graphical partition of order  is one for which the sum of degrees is . A -graphical partition only exists for even .

It is possible for two topologically distinct graphs to have the same degree sequence, an example of which is illustrated above.

The numbers of graphical partitions  on , 4, 6, ... edges are 1, 2, 5, 9, 17, 31, 54, 90, 151, 244, ... (OEIS A000569).

Erdős and Richmond (1989) showed that

and

---

REFERENCES

Barnes, T. M. and Savage, C. D. "A Recurrence for Counting Graphical Partitions." Electronic J. Combinatorics 2, No. 1, R11, 1-10, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1r11.html.

Barnes, T. M. and Savage, C. D. "Efficient Generation of Graphical Partitions." Disc. Appl. Math. 78, 17-26, 1997.

Erdős, P. and Richmond, L. B. "On Graphical Partitions." Combinatorics and Optimization Research Report COPR 89-42.

Waterloo, Ontario: University of Waterloo, pp. 1-13, 1989.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 57, 1994.

Ruskey, F. "Information on Graphical Partitions." http://www.theory.csc.uvic.ca/~cos/inf/nump/GraphicalPartition.html.

Sloane, N. J. A. Sequences A000569, A002494/M1762, and A095268 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics, Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993 (Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge University Press, pp. 557-562, 1997.

اخر الاخبار

اخبار العتبة العباسية المقدسة

مجموعة العميد التربوية تعقد اجتماعًا لمناقشة الاستعدادات الخاصة بالموسم التدريبي الصيفي

قسم الإعلام ينظم ورشة تدريبية حول تطبيق (إعلامي) لعدد من منتسبي قسم حفظ النظام

قسم الشؤون الخدمية ينفذ حملة لتنظيف الشوارع المحيطة بصحن مرقد أبي الفضل العباس (عليه السلام)

وفد العتبة العباسية المقدسة يزور شعبة الإعداد البدني للاطّلاع على برنامج تأهيل المنتسبين الجدد

المزيد

الآخبار الصحية

ماذا يحدث إذا تناولنا الطعام مرة واحدة فقط في اليوم

اكتشاف عوامل خطر غير متوقعة لمرض الكبد الدهني

فيروس هانتا والسفينة الموبوءة.. تحديث من الصحة العالمية

طبيب يحسم الجدل السجائر الإلكترونية وعلاقتها بالسرطان

المزيد

الآخبار التكنلوجية

لأول مرة في الولايات المتحدة.. تشغيل مفاعل مصغر نووي يغذي الذكاء الاصطناعي بالطاقة

الكشف عن تفاصيل أول عملية ناجحة لاستعادة انتاج الحيوانات المنوية

أطلس يكشف خفايا الجسم البشري بدقة أرفع بـ50 مرة من شعر الإنسان

المتحف المصري الكبير يتحول إلى "أيقونة خضراء" بدعم ياباني

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength