Labeled Graph

 

A labeled graph  is a finite series of graph vertices  with a set of graph edges  of 2-subsets of . Given a graph vertex set {1,2,...,n}" src="https://mathworld.wolfram.com/images/equations/LabeledGraph/Inline5.svg" style="height:22px; width:137px" />, the number of vertex-labeled graphs is given by . Two graphs  and  with graph vertices {1,2,...,n}" src="https://mathworld.wolfram.com/images/equations/LabeledGraph/Inline9.svg" style="height:22px; width:137px" /> are said to be isomorphic if there is a permutation  of  such that {u,v}" src="https://mathworld.wolfram.com/images/equations/LabeledGraph/Inline12.svg" style="height:22px; width:41px" /> is in the set of graph edges  iff {p(u),p(v)}" src="https://mathworld.wolfram.com/images/equations/LabeledGraph/Inline14.svg" style="height:22px; width:97px" /> is in the set of graph edges .

The term "labeled graph" when used without qualification means a graph with each node labeled differently (but arbitrarily), so that all nodes are considered distinct for purposes of enumeration. The total number of (not necessarily connected) labeled -node graphs for , 2, ... is given by 1, 2, 8, 64, 1024, 32768, ... (OEIS A006125; illustrated above), and the numbers of connected labeled graphs on -nodes are given by the logarithmic transform of the preceding sequence, 1, 1, 4, 38, 728, 26704, ... (OEIS A001187; Sloane and Plouffe 1995, p. 19).

The numbers of graph vertices in all labeled graphs of orders , 2, ... are 1, 4, 24, 256, 5120, 196608, ... (OEIS A095340), which the numbers of edges are 0, 1, 12, 192, 5120, 245760, ... (OEIS A095351), the latter of which has closed-form

---

REFERENCES

Cahit, I. "Homepage for the Graph Labelling Problems and New Results." http://www.emu.edu.tr/~cahit/CORDIAL.htm.

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.

Gilbert, E. N. "Enumeration of Labeled Graphs." Canad. J. Math. 8, 405-411, 1956.

Harary, F. "Labeled Graphs." Graph Theory. Reading, MA: Addison-Wesley, pp. 10 and 178-180, 1994.

Harary, F. and Palmer, E. M. "Labeled Enumeration." Ch. 1 in Graphical Enumeration. New York: Academic Press, pp. 1-31, 1973.

Sloane, N. J. A. Sequences A001187/M3671, A006125/M1897, A095340 and A095351 in "The On-Line Encyclopedia of Integer Sequences.

"Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.

اخر الاخبار

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

جمعية كشافة الكفيل: المجالس الحسينية تعلّم الفتية قيم نهضة الإمام الحسين (عليه السلام)

عَبرَ المجالس الحسينية.. المجمَع العلمي يقدّم محاضرات دينية وتلاوات قرآنية في بغداد والنجف وميسان

برعاية العتبة العباسية المقدسة.. موكب قناديل السماء يُحيي مراسم اليوم الثالث عشر من المحرّم

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

المزيد

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

لكبح الجوع وخسارة الوزن.. "سر بسيط" في نظام جوكوفيتش ؟

هل يساعد الرجيم في علاج الأمراض العقلية؟

لحماية أسنان طفلك.. هذا الفيتامين يقلل خطر التسوس

أكل الطعام بسرعة.. طريق سريع إلى أمراض خطيرة

المزيد

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

ما هي أفضل درجة حرارة لتكييف الهواء في السيارة؟

ذوبان الأنهار الجليدية يوقظ "عمالقة نائمة"!

9 يوليو يشهد أقصر يوم في التاريخ المسجل ؟!!

راتبه عشرات ملايين الدولارات.. زوكربرغ يخطف "عقل أبل"

المزيد

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

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