Algorithmic study of d2-transitivity of graphs

Let G = (V, E) be a graph, where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V, we say A dominates B if every vertex of B is adjacent to at least one vertex of A. In this article, we initiate the study of a generalization of transitive partition, namely d2-transitive partition. For two disjoint subsets A and B of V, we say A d2dominates B if, for every vertex of B, there exists a vertex in A such that the distance between them is at most two. A vertex partition π = V1, V2,. . . , V k of G is said to be a d2-transitive partition of size k if Vi d2-dominates Vj for all 1 ≤ i < j ≤ k. The maximum integer k for which d2-transitive partition exists is called d2-transitivity of G, and it is denoted by T r d 2 (G). The M d2-T P is to find a d2-transitive partition of a given graph with the maximum number of parts. We show that this problem can be solved in linear time for the complement of bipartite graphs and bipartite chain graphs. On the other side, we prove that the decision version of the M d2-T P is NP-complete for split graphs and bipartite graphs.