论文标题
两分图的亚类的传播
Transitivity on subclasses of bipartite graphs
论文作者
论文摘要
令$ g =（v，e）$是一个图，其中$ v $和$ e $分别为顶点和边缘集。对于两个不相交的子集$ a $和$ b $，我们说，如果每个顶点$ b $都与至少一个顶点$ a $相邻，则说明$ a $ b $。一个顶点分区$π= \ {v_1，v_2，\ ldots，\ ldots，v_k \} $ of $ g $的$ g $称为a \ emph {transitive $ k $ -partition}，如果$ v_i $ ponistion $ v_i $ ponistaines $ v_j $ to $ i，j $ i，j $ j $ where $ 1 \ leq i <j i <j i <j i <j \ j \ j \ leq k $。上述分区的最大整数$ k $称为$ g $的\ emph {pransitivitive}，它用$ tr（g）$表示。 \ textsc {最大传递性问题}是找到具有最大分区数的给定图的及传递分区。众所周知，\ textsc {最大传递性问题}的决策版本对于一般图是NP完整的，这是Hedetniemi等人证明的。 [图形的迭代着色，\ emph {iNcteeth Mathematics}，278，2004]。本文首先通过证明此问题仍然是NP完整的，以实现NP的完整性，从而增强了NP的完整性。另一方面，我们提出了一种线性时间算法，用于查找给定的两分链图的传递性。然后，我们对任何整数$ t $的图表至少至少$ t $。该结果回答了J. T. Hedetniemi和S. T. Hedetniemi提出的两个空旷的问题[图形的传递性，\ emph {j。组合。数学。组合。计算}，104，2018]。
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, \ldots, V_k\}$ of $G$ is called a \emph{transitive $k$-partition} if $V_i$ dominates $V_j$ for all $i,j$ where $1\leq i<j\leq k$. The maximum integer $k$ for which the above partition exists is called \emph{transitivity} of $G$ and it is denoted by $Tr(G)$. The \textsc{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 \textsc{Maximum Transitivity Problem} is NP-complete for general graphs, which was proved by Hedetniemi et al. [Iterated colorings of graphs, \emph{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, \emph{J. Combin. Math. Combin. Comput}, 104, 2018].
