On total transitivity of graphs

Abstract

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 that $A$ \emph{dominates} $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$. A vertex partition $\pi =\{V_1,V_2,\dots ,V_k\}$ of $G$ is called a \emph{transitive partition} of size $k$ if $V_i$ dominates $V_j$ for all $1\le i<j\le k$. In this article, we study a variation of the transitive partition, namely the \emph{total transitive partition}. The total transitivity $T{r}_t(G)$ is defined as the maximum order of a vertex partition $\pi =\{V_1,V_2,\dots ,V_k\}$ of $G$ obtained by repeatedly removing a total dominating set from $G$ until no vertices remain. Thus, $V_1$ is a total dominating set of $G$, $V_2$ is a total dominating set of the graph $G_1=G-V_1$, and, for $2\le i\le k-1$, $V_{i+1}$ is a total dominating set in the graph $G_i=G-{\bigcup }_{j=1}^i{V}_j$. A vertex partition of order $T{r}_t(G)$ is called a $T{r}_t$-partition. The \textsc{Maximum Total Transitivity Problem} is to find a total transitive partition of a given graph with the maximum number of parts. First, we characterize split graphs with total transitivity equal to $1$ and $\omega (G)-1$. Moreover, for a split graph $G$ and $1\le p\le \omega (G)-1$, we provide necessary conditions for $T{r}_t(G)=p$. Furthermore, we show that the decision version of this problem is NP-complete for bipartite graphs. On the positive side, we prove that this problem can be solved in linear time for bipartite chain graphs. Finally, we design a polynomial-time algorithm to solve the \textsc{Maximum Total Transitivity Problem} in trees.