Publication: Interpolation theorems in jump graphs
2
0
Issued Date
2007
Resource Type
File Type
application/pdf
ISSN
10344942
Other identifier(s)
2-s2.0-70349976760
Rights Holder(s)
มหาวิทยาลัยศรีนครินทรวิโรฒ
Bibliographic Citation
Australasian Journal of Combinatorics. Vol 39, No.1 (2007), p.103-114
Suggested Citation
Punnim N. Interpolation theorems in jump graphs. Australasian Journal of Combinatorics. Vol 39, No.1 (2007), p.103-114. Retrieved from: https://hdl.handle.net/20.500.14740/4248
Author(s)
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.