Graph Expansion
المؤلف:
Biggs, N. L
المصدر:
Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press
الجزء والصفحة:
...
10-4-2022
2134
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 ![<span style=]()
{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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
