Publications
Detailed Information
Competitively orientable complete multipartite graphs
Cited 1 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Issue Date
- 2022-09
- Publisher
- Elsevier BV
- Citation
- Discrete Mathematics, Vol.345 No.9, p. 112950
- 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 competition graph of a digraph D is defined as the graph with the vertex set V (D) and an edge uv if and only if u and v compete in D. The notion of competitive digraph 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. (C) 2022 Elsevier B.V. All rights reserved.
- ISSN
- 0012-365X
- Files in This Item:
- There are no files associated with this item.
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.