Graph Expansion

Given any tree  having  vertices of vertex degrees of 1 and 3 only, form an -expansion by taking  disjoint copies of  and joining corresponding leaves by an -cycle where, however, the th leaf on the th copy need not be connected to the th leaf on the st copy, but will in general be connected to the th copy. The set of values {s_1,...,s_v}" src="https://mathworld.wolfram.com/images/equations/GraphExpansion/Inline12.svg" style="height:22px; width:83px" /> are known as the steps.

The resulting graphs are always cubic, and there exist exactly 13 graph expansions that are symmetric as well, as summarized in the following table (Biggs 1993, p. 147). E. Gerbracht (pers. comm., Jan. 29, 2010) has shown that all the graphs in this table are unit-distance.

	graph	Foster	generalized Petersen graph	base graph	expansion
8	cubical graph			I graph	(4; 1, 1)
10	Petersen graph			I graph	(5; 1, 2)
16	Möbius-Kantor graph			I graph	(8; 1, 3)
20	dodecahedral graph			I graph	(10; 1, 2)
20	Desargues graph			I graph	(10; 1, 3)
24	Nauru graph			I graph	(12; 1, 5)
28	Coxeter graph			Y graph	(7; 1, 2, 4)
48	cubic symmetric graph			I graph	(24; 1, 5)
56	cubic symmetric graph			Y graph	(14; 1, 3, 5)
102	Biggs-Smith graph			H graph	(17; 3, 5, 6, 7)
112	cubic symmetric graph			Y graph	(28; 1, 3, 9)
204	cubic symmetric graph			H graph	(34; 3, 5, 7, 11)
224	cubic symmetric graph			Y graph	(56; 1, 9, 25)

---

REFERENCES

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 147, 1993.

Horton, J. D. and Bouwer, I. Z. "Symmetric Y-Graphs and H-Graphs." J. Combin. Th. Ser. B 53, 114-129, 1991.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

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

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