Graph Expansion

Given any tree T having v vertices of vertex degrees of 1 and 3 only, form an n-expansion by taking n disjoint copies of T and joining corresponding leaves by an n-cycle where, however, the kth leaf on the ith copy need not be connected to the kth leaf on the (i+1)st copy, but will in general be connected to the (i+s_k)th copy. The set of values {s_1,...,s_v} 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.

See also

Biggs-Smith Graph, Edge Contraction, H Graph, I Graph, Y Graph

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Graph Expansion

Cite this as:

Weisstein, Eric W. "Graph Expansion." From MathWorld--A Wolfram Web Resource.

Subject classifications