Generalization of bipartite graphs

Let G = (V, E) be a graph with set of vertices V and set of edges E. An independent set in G is a subset S of V such that no two vertices of S are mutually adjacent. E. Sampathkumar et al. (2003) gave a generalization of independent sets. In this context, we define graph G = V, E) is said to be k-distance bipartite (or Dk-bipartite) if its vertex set can be partitioned into two Dk independent sets. If the diameter of G is < k, then G is distance k-bipartite and so if G is not distance k-bipartite then diameter of G is at least k. Given any integer k > 0, we can associate a graph G(k) as follows: The DK-graph of G, denoted by G(k) is the graph on same vertex set V and two vertices u and v are adjacent if and only if distance between them is equal to k. Clearly, a graph is Dk-bipartite if and only if G(k) is bipartite. In this paper, we presented several characterizations of k-distance bipartite graphs.