Jump graph

Jump graph --- прыгающий граф, граф скачков.

Let [math]\displaystyle{ G }[/math] be a graph of size [math]\displaystyle{ q }[/math], where [math]\displaystyle{ q \geq 1 }[/math], and let [math]\displaystyle{ F }[/math] and [math]\displaystyle{ H }[/math] be edge-induced subgraphs of size [math]\displaystyle{ k }[/math] [math]\displaystyle{ (1 \leq k \leq q) }[/math] in [math]\displaystyle{ G }[/math]. We say that [math]\displaystyle{ H }[/math] is obtained from [math]\displaystyle{ F }[/math] by an edge jump if there exist four distinct vertices [math]\displaystyle{ v,u,w }[/math] and [math]\displaystyle{ x }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ (u,v) \in E(G) }[/math], [math]\displaystyle{ (w,x) \in E(G) - E(F) }[/math], and [math]\displaystyle{ H = F - (u,v) + (w,x) }[/math]. For any two subgraphs [math]\displaystyle{ F }[/math] and [math]\displaystyle{ H }[/math] in the graph [math]\displaystyle{ G }[/math], we say that [math]\displaystyle{ F }[/math] is [math]\displaystyle{ j }[/math]-transformed into [math]\displaystyle{ H }[/math] if [math]\displaystyle{ H }[/math] can be obtained from [math]\displaystyle{ F }[/math] by a sequence of [math]\displaystyle{ j }[/math] edge jumps. The minimum number of edge jumps required to transform [math]\displaystyle{ F }[/math] into [math]\displaystyle{ H }[/math] is called the jump distance [math]\displaystyle{ d_{j}(F,H) }[/math] from [math]\displaystyle{ F }[/math] to [math]\displaystyle{ H }[/math]. The [math]\displaystyle{ k }[/math]-jump graph [math]\displaystyle{ J_{k}(G) }[/math] of [math]\displaystyle{ G }[/math] is such a graph whose vertices are the [math]\displaystyle{ \left(\begin{array}{c} q \\ k \end{array}\right) }[/math] edge-induced subgraphs of size [math]\displaystyle{ k }[/math], that two vertices [math]\displaystyle{ F }[/math] and [math]\displaystyle{ H }[/math] of [math]\displaystyle{ J_{k}(G) }[/math] are adjacent if [math]\displaystyle{ d_{j}(F,H) = 1 }[/math]. If [math]\displaystyle{ k = 1 }[/math], then we refer to [math]\displaystyle{ J_{k}(G) = J_{1}(G) }[/math] as a jump graph of [math]\displaystyle{ G }[/math] and denote this more simply by [math]\displaystyle{ J(G) }[/math]. It is known that [math]\displaystyle{ J(G) }[/math] is the complement of the line graph [math]\displaystyle{ L(G) }[/math] of [math]\displaystyle{ G }[/math].