

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。