Geodesic
The niche graphs of multipartite tournaments
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1123-1146

Voir la notice de l'article provenant de la source Library of Science

The niche graph of a digraph D has V(D) as the vertex set and an edge uv if and only if (u,w) ∈ A(D) and (v,w) ∈ A(D), or (w,u) ∈ A(D) and (w,v) ∈ A(D) for some w ∈ V(D). The notion of niche graphs was introduced by Cable et al. [Niche graphs, Discrete Appl. Math. 23 (1989), 231–241] as a variant of competition graphs. If a graph is the niche graph of a digraph D, it is said to be niche-realizable through D. If a graph G is niche-realizable through a k-partite tournament for an integer k ≥ 2, then we say that the pair (G, k) is niche-realizable. Bowser et al. [Niche graphs and mixed pair graphs of tournaments, J. Graph Theory 31 (1999) 319–332] studied the graphs that are niche-realizable through a tournament and Eoh et al. [The niche graphs of bipartite tournaments, Discrete Appl. Math. 282 (2020) 86–95] recently studied niche-realizable pairs (G, k) for k=2. In this paper, we extend their work for k ≥ 3. We show that the niche graph of a k-partite tournament has at most three components if k ≥ 3 and is connected if k ≥ 4. Then we find all the niche-realizable pairs (G, k) in each case: G is disconnected; G is a complete graph; G is connected and triangle-free.
Keywords: niche graph, multipartite tournament, niche-realizable pair, true twins, triangle-free graph 
@article{DMGT_2023_43_4_a13,
     author = {Eoh, Soogang and Choi, Myungho and Kim, Suh-Ryung},
     title = {The niche graphs of multipartite tournaments},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1123--1146},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a13/}
}
TY  - JOUR
AU  - Eoh, Soogang
AU  - Choi, Myungho
AU  - Kim, Suh-Ryung
TI  - The niche graphs of multipartite tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1123
EP  - 1146
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a13/
LA  - en
ID  - DMGT_2023_43_4_a13
ER  - 
%0 Journal Article
%A Eoh, Soogang
%A Choi, Myungho
%A Kim, Suh-Ryung
%T The niche graphs of multipartite tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1123-1146
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a13/
%G en
%F DMGT_2023_43_4_a13
Eoh, Soogang; Choi, Myungho; Kim, Suh-Ryung. The niche graphs of multipartite tournaments. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1123-1146. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a13/