Hoffman-Singleton Theorem

 

Let  be a -regular graph with girth 5 and graph diameter 2. (Such a graph is a Moore graph). Then, , 3, 7, or 57. A proof of this theorem is difficult (Hoffman and Singleton 1960, Feit and Higman 1964, Damerell 1973, Bannai and Ito 1973), but can be found in Biggs (1993).

The first three are the cycle graph  (), Petersen graph (), and Hoffman-Singleton graph (). The existence of the last is an unsolved problem.

---

REFERENCES

Bannai, E. and Ito, T. "On Moore Graphs." J. Fac. Sci. Univ. Tokyo Ser. A 20, 191-208, 1973.

Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Damerell, R. M. "On Moore Graphs." Proc. Cambridge Philos. Soc. 74, 227-236, 1973.

Feit, W. and Higman, G. "The Non-Existence of Certain Generalized Polygons." J. Algebra 1, 114-131, 1964.

Hoffman, A. J. and Singleton, R. R. "On Moore Graphs of Diameter Two and Three." IBM J. Res. Develop. 4, 497-504, 1960.

اخر الاخبار

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

سماحة السيد الصافي يكرم عددًا من عوائل الشهداء ضمن فعاليات مهرجان روح النبوة النسوي العالمي الثامن

إحدى أمهات الشهداء: نعتز بتضحيات أبنائنا ونفتخر بشهادتهم دفاعًا عن الدين والمقدسات

ضمن فعاليات مهرجان روح النبوة… عرض فيلم يوثق نشاطات الشعب النسوية في العتبة العباسية المقدسة

فعاليات مهرجان روح النبوة الثقافي تشهد تقديم أوبريت الثقلين القرآني

المزيد

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

ماذا يحدث لجسمك عند تناول الوجبات السريعة يوميا؟

لصحة عظام المرأة.. الشاي أفضل أم القهوة؟

لبناء العضلات وإنقاص الوزن.. ما أفضل توقيت لتناول البيض؟

أطعمة صحية تساعد على التعافي من "الإنفلونزا الخارقة"

المزيد

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

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

تجربة جديدة: الأسفلت المدعوم بالطحالب يقاوم الحفر ويقلل الانبعاثات الكربونية

تسريبات تكشف ملامح أول هاتف قابل للطي من "أبل"

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

المزيد

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

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