Inflation

Inflation --- инфляция.

1. The inflation [math]\displaystyle{ G_{l} }[/math] of a graph [math]\displaystyle{ G }[/math] is the line graph of a subdivision of [math]\displaystyle{ G }[/math].

2. Let [math]\displaystyle{ F }[/math] and [math]\displaystyle{ G }[/math] be (simple) graphs such that [math]\displaystyle{ V(G) = \{v_{1}, \ldots, v_{n}\} }[/math]. We say that [math]\displaystyle{ F }[/math] is an inflation if [math]\displaystyle{ V(F) }[/math] can be written as a disjoint union [math]\displaystyle{ V(F) = V_{1} \cup \cdots \cup V_{n} }[/math] in such a way that if [math]\displaystyle{ x \in V_{i} }[/math] and [math]\displaystyle{ y \in V_{j} }[/math], then [math]\displaystyle{ xy \in E(F) }[/math] if and only if [math]\displaystyle{ i = j }[/math] or [math]\displaystyle{ v_{i}v_{j} \in E(G) }[/math]. (So to inflate a graph is to replace each vertex by a complete graph.) If [math]\displaystyle{ |V_{i}| = t }[/math] for all [math]\displaystyle{ t }[/math], then we write [math]\displaystyle{ F = G_{(i)} }[/math] and call it a uniform inflation of [math]\displaystyle{ G }[/math]. (Another way of looking at [math]\displaystyle{ G_{(i)} }[/math] is considering it as a lexicographic product or composition [math]\displaystyle{ G[K_{t}] }[/math] of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ K_{t} }[/math], also called the wreath product [math]\displaystyle{ G * K_{t} }[/math]).