论文标题
在图表的单声道等级上
On the monophonic rank of a graph
论文作者
论文摘要
图$ g $的一组顶点$ s $是$单声道\ convex $，如果每一个连接两个$ s $的顶点的路径都包含在$ s $中。 $ sonophonic \ convex \ hull $ of $ s $，$ \ langle s \ rangle $，是包含$ s $的最小单声音凸集。 a seet $ s $是$ nophonic \ convexly \独立$，如果$ v \ not \ in \ langle s- \ \ {v \} \ rangle $ in s $中的每个$ v \。 $ nonophonic \ rank $ $ g $的排名是$ g $的最大单声音独立套件的大小。我们提出了单声音凸的独立集的表征。使用此结果，我们展示了如何在多项式时间内确定图形类别，仙人掌，无三角形和线形的单声道等级。此外，我们证明可以在多项式时间内以$ 1 $ - 星形的图，$，即$，用于拆分图，并且其确定为$ np $ -complete，对于任何固定的$ k \ ge 2 $，Chordal of Chordal图。我们还在图形上考虑了此问题，其最大素数的相交图是一棵树。
A set of vertices $S$ of a graph $G$ is $monophonically \ convex$ if every induced path joining two vertices of $S$ is contained in $S$. The $monophonic \ convex \ hull$ of $S$, $\langle S \rangle$, is the smallest monophonically convex set containing $S$. A set $S$ is $monophonic \ convexly \ independent$ if $v \not\in \langle S - \{v\} \rangle$ for every $v \in S$. The $monophonic \ rank$ of $G$ is the size of the largest monophonic convexly independent set of $G$. We present a characterization of the monophonic convexly independent sets. Using this result, we show how to determine the monophonic rank of graph classes like bipartite, cactus, triangle-free and line graphs in polynomial time. Furthermore, we show that this parameter can be computed in polynomial time for $1$-starlike graphs, $i.e.$, for split graphs, and that its determination is $NP$-complete for $k$-starlike graphs for any fixed $k \ge 2$, a subclass of chordal graphs. We also consider this problem on the graphs whose intersection graph of the maximal prime subgraphs is a tree.
