Competitively orientable complete multipartite graphs

2020/06/21 by Myungho Choi, Choi, Myungho, Minki Kwak +3 · 1 citation
Computer Science · Decision Sciences · #05C20 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2006.11743

openalex publication_date 2020/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 n ≥ 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.

Cited by

• The triangle-free graphs which are competition graphs of multipartite tournaments

Related

• Multipartite tournaments in which any two vertices have an (i,j)-step common out-neighbor
• The niche graphs of multipartite tournaments
• On (1,2)-step competition graphs of multipartite tournaments
• Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
• Partitioning transitive tournaments into isomorphic digraphs