Competitively orientable complete multipartite graphs

DOI10.1016/J.DISC.2022.112950MaRDI QIDQ6343368arXivFDO

Authors Myungho Choi, Minki Kwak, Suh-Ryung Kim

Publication date 21 June 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.112950

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

arXiv classification

math.CO

Abstract: 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 $ngeq7$. 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.

This page was built for publication: Competitively orientable complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343368)