Interpolation theorems in jump graphs

Abstract

For positive integers m and n (1 ≤ m ≤ (n 2)), let Jm(n) be the class of all distinct subgraphs of Kn of size m. Let G,H ∈ Im(n). Then G is said to be obtained from H by an edge jump if there exist four distinct vertices u,v,w, and x of Kn such that e = uv ∉ E(H), f = wx ∈ E(H) and σ(e,f)H:= H + e -/= G. The minimum number of edge jumps required to transform H to G is the jump distance from H to G. The graph Jm(n) is that graph having Jm(n) as its vertex set where two vertices of Jm(n) are adjacent if and only if the jump distance between the corresponding subgraphs is 1. Let ℂm(n) be the subset of Jm(n) consisting of all connected graphs. We prove in this paper that the graph Jm(n) is connected and the subgraph of the graph Jm(n) induced by ℂm(n) is also connected. Several graph parameters are proved to interpolate over the class Jm(n) and ℂm (n). Algorithms for determining the extreme values for the chromatic number X and the clique number are also provided.