Transitivity on subclasses of bipartite graphs
share
Let G=(V, E) be a graph where V and E are the vertex and edge set, respectively. For two disjoint subsets A and B, we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = {V_1, V_2, …, V_k} of G is called a transitive k-partition if V_i dominates V_j for all i,j where 1≤ i<j≤ k. The maximum integer k for which the above partition exists is called 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 the maximum number of partitions. It was known that the decision version of Maximum Transitivity Problem is NP-complete for general graphs, which was proved by Hedetniemi et al. [Iterated colorings of graphs, Discrete Mathematics, 278, 2004]. This paper first strengthens the NP-completeness result by showing that this problem remains NP-complete for perfect elimination bipartite graphs. On the other hand, we propose a linear-time algorithm for finding the transitivity of a given bipartite chain graph. We then characterize graphs with transitivity at least t for any integer t. This result answers two open questions posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, J. Combin. Math. Combin. Comput, 104, 2018].
READ FULL TEXT