Generalization of bipartite graphs

AbstractLet G= (V, E) be a graph with set of vertices Vand set of edges E. An independent set in Gis a subset Sof Vsuch that no two vertices of Sare 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 Dkindependent sets. If the diameter of Gis < k, then Gis distance k-bipartite and so if Gis not distance k-bipartite then diameter of Gis 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 Vand two vertices uand vare 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.