Geodetic Graph

Ore (1962) noted that not only does a tree possesses a unique shortest path between any two vertices, but that there also exist also other connected graphs having the same property. He termed all such graphs "geodetic graphs" and asked for a characterization of such graphs.

The numbers of geodetic graphs on , 2, ... nodes are 1, 1, 2, 4, 10, 23, 66, 185, 586, 1880, 6360, ... (OEIS A337179).

Examples of geodetic graphs include barbell graphs, cacti graph lacking even cycles (Gorovoy and Zmiaikou 2021), complete graphs  (Gorovoy and Zmiaikou 2021), odd cycle graphs  (Gorovoy and Zmiaikou 2021), lollipop graphs, trees (Gorovoy and Zmiaikou 2021), triangular snake graphs, and windmill graphs.

---

REFERENCES

Frasser, C. E. "-Geodetic Graphs and Their Application to the Topological Design of Computer Networks." In Proc. Argentinian Workshop on Theoretical Computer Science, 28 JAIIO-WAIT'99. pp. 187-203, 1999.

Gorovoy, D. and Zmiaikou, D. "On Graphs with Unique Geoodesics and Antipodes." 19 Nov 2021. https://arxiv.org/abs/2111.09987.

Ore, O. Theory of Graphs. Providence, RI: Amer. Math. Soc., 1962.

Parthasarathy, K. R. and Srinivasan, N. "Some General Constructions of Geodetic Blocks." J. Combin. Th. 33, 121-136, 1982.

Sloane, N. J. A. Sequence A337179 in "The On-Line Encyclopedia of Integer Sequences."Stemple, J. G.; and Watkins, M. E. "On Planar Geodetic Graphs." J. Combin. Th. 4, 101-117, 1968.

اخر الاخبار

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

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

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

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

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

المزيد

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

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

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

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

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

المزيد

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

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

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

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