Generalization of bipartite graphs. (2nd April 2020)

• Record Type: Journal Article
• Authors: Reddy, P. Siva Kota; Hemavathi, P. S.
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 23:Number 3(2020)
• Page Start: 787
• Page End: 793
• Publication Date: 2020-04-02
• Subjects: 05C12; Graphs -- Independent set -- Bipartite graph -- Dk-graph -- (i, j)-bipartite; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2019.1701269
• Languages: English
• ISSNs: 0972-0529

Abstract

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.