TOPICS
Search

Graph Blow-Up

A graph blow-up of a graph H with vertices v_1, v_2, ..., v_p is a graph obtained by replacing each vertex v_i by a nonempty independent vertex set V_i and replacing each graph edge v_iv_j by all the edges of the complete bipartite graph with parts V_i and V_j (Illingworth 2022). There are no other edges. Thus all vertices in a given set V_i have the same neighbors outside that set.

If |V_i|=m_i, the resulting graph is often denoted H[m_1,m_2,...,m_p]. Its graph order and edge count are

|V(H[m_1,m_2,...,m_p])|=sum_(i=1)^pm_i,

and

|E(H[m_1,m_2,...,m_p])|=sum_(v_iv_j in E(H))m_im_j.

When all m_i=t, the blow-up is called uniform and is denoted H(t) by some authors. This exact-equality case is also called a balanced blow-up (Hatami et al. 2014). It is the graph lexicographic product H-K^__t, where K^__t is the empty graph on t vertices. When the total order is fixed but is not necessarily divisible by p, "balanced" is also used when the fiber sizes differ by at most one (Avigad and Goldreich 2011).

Blow-ups of complete graphs are precisely the complete multipartite graphs. In particular, balanced blow-ups of complete graphs are Turán graphs.

This graph operation is distinct from algebraic blow-up and finite-time blow-up, and from the blow-up lemma, which concerns embedding graphs into regular pairs that approximate the complete bipartite pairs of a graph blow-up.

See also

Algebraic Blow-Up, Blow-Up, Blow-Up Lemma, Complete Multipartite Graph, Finite-Time Blow-Up, Graph Lexicographic Product

Explore with Wolfram|Alpha

References

Avigad, L. and Goldreich, O. "Testing Graph Blow-Up." In Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation (Ed. O. Goldreich). Berlin, Germany: Springer-Verlag, pp. 156-172, 2011. https://doi.org/10.1007/978-3-642-22670-0_18.Hatami, H.; Hirst, J.; and Norine, S. "The Inducibility of Blow-Up Graphs." J. Combin. Th. Ser. B 109, 196-212, 2014. https://doi.org/10.1016/j.jctb.2014.06.005.Illingworth, F. "The Chromatic Profile of Locally Colourable Graphs." Combinatorics, Probability and Computing 31, 976-1009, 2022. https://doi.org/10.1017/S0963548322000050.

Cite this as:

Weisstein, Eric W. "Graph Blow-Up." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphBlow-Up.html

Subject classifications