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 G. A vertex partition \(\pi = \{V_1, V_2, \ldots , V_k\}\) of G is called a transitive partition of size k if \(V_i\) dominates \(V_j\) for all i, j, where \(1\le i<j\le k\) . The maximum integer k for which the above partition exists is called the transitivity of G, and it is denoted by Tr(G). The Maximum Transitivity Problem is to find a transitive partition of a given graph with maximum number of sets in the partition. In this paper, we first prove that the Maximum Transitivity Problem problem can be solved in linear time for split graphs, pseudo-split graphs and the complement of bipartite chain graphs. Then we discuss Nordhaus-Gaddum type relations for transitivity and provide counterexamples to an open problem posed by Hedetniemi and Hedetniemi [The transitivity of a graph, J. Combin. Math. Combin. Comput., 104, 2018]. We then study the transitivity for central graphs, and as a consequence, we have identified a few graph classes for which transitivity is equal to the Grundy number, which was mentioned as an open problem in the above-mentioned paper. Finally, we study transitively critical graphs and characterize the critical graphs having fixed transitivity.
