























A vertex partition $π= \{V_1, V_2, \ldots, V_k\}$ of $G$ is called a \emph{transitive partition} of size $k$ if $V_i$ dominates $V_j$ for all $1\leq i<j\leq k$. For two disjoint subsets $A$ and $B$ of $V$, we say $A$ \emph{strongly dominates} $B$ if for every vertex $y\in B$, there exists a vertex $x\in A$, such that $xy\in E$ and $deg_G(x)\geq deg_G(y)$. A vertex partition $π= \{V_1, V_2, \ldots, V_k\}$ of $G$ is called a \emph{strong transitive partition} of size $k$ if $V_i$ strongly dominates $V_j$ for all $1\leq i<j\leq k$. The \textsc{Maximum Strong Transitivity Problem} is to find a strong transitive partition of a given graph with the maximum number of parts. In this article, we initiate the study of this variation of transitive partition from algorithmic point of view. We show that the decision version of this problem is NP-complete for chordal graphs. On the positive side, we prove that this problem can be solved in linear time for trees and split graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。