Generalization of bipartite graphs. (2nd April 2020) - Reddy, P. Siva Kota; Hemavathi, P. S.
Abstract: 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.