论文标题
竞争性定向的完整多部分图
Competitively orientable complete multipartite graphs
论文作者
论文摘要
我们说，如果任何一对顶点在$ d $中具有共同的邻居外，并且图$ g $在竞争性方向上是$ g $，则可以在$ d $ $ d $中进行竞争。在研究竞争图的挖掘时，出现了竞争性挖掘的概念。我们获得了竞争性方向图的一些有用的属性，并在且仅当$ n \ geq 7 $时就可以在订单$ n $的完整图上取向。然后，我们完全根据其党集的大小来表征一个可竞争性的完整多部分图。此外，我们提出了一种在每个竞争性定向的案例中建立竞争性的多方比赛的方法。
We say that a digraph $D$ is competitive if any pair of vertices has a common out-neighbor in $D$ and that a graph $G$ is competitively orientable if there exists a competitive orientation of $G$. The notion of competitive digraphs arose while studying digraph whose competition graphs are complete. We derive some useful properties of competitively orientable graphs and show that a complete graph of order $n$ is competitively orientable if and only if $n \geq 7$. Then we completely characterize a competitively orientable complete multipartite graph in terms of the sizes of its partite sets. Moreover, we present a way to build a competitive multipartite tournament in each of competitively orientable cases.
