Geodesic
The niche graphs of multipartite tournaments
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1123-1146 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {4},
     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
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
%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/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Ed. (Springer-Verlag, London, 2009). https://doi.org/10.1007/978-1-84800-998-1

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982).

[3] S. Bowser and C. Cable, Some recent results on niche graphs, Discrete Appl. Math. 30 (1991) 101–108. https://doi.org/10.1016/0166-218X(91)90036-V

[4] S. Bowser, C. Cable and R. Lundgren, Niche graphs and mixed pair graphs of tournaments, J. Graph Theory 31 (1999) 319–332. https://doi.org/10.1002/(SICI)1097-0118(199908)31:43.0.CO;2-S

[5] C. Cable, K.F. Jones, R. Lundgren and S. Seager, Niche graphs, Discrete Appl. Math. 23 (1989) 231–241. https://doi.org/10.1016/0166-218X(89)90015-2

[6] H.H. Cho, S-R. Kim and Y. Nam, The m-step competition graph of a digraph, Discrete Appl. Math. 105 (2000) 115–127. https://doi.org/10.1016/S0166-218X(00)00214-6

[7] J.E. Cohen, Interval graphs and food webs: a finding and a problem (RAND Corporation Document 17696-PR, Santa Monica, CA, 1968).

[8] S. Eoh, J. Choi, S-R. Kim and M. Oh, The niche graphs of bipartite tournaments, Discrete Appl. Math. 282 (2020) 86–95. https://doi.org/10.1016/j.dam.2019.11.001

[9] K.A. Factor and S.K. Merz, The (1,2)-step competition graph of a tournament, Discrete Appl. Math. 159 (2011) 100–103. https://doi.org/10.1016/j.dam.2010.10.008

[10] P.C. Fishburn and W.V. Gehrlein, Niche numbers, J. Graph Theory 16 (1992) 131–139. https://doi.org/10.1002/jgt.3190160204

[11] S.-R. Kim, T.A. McKee, F.R. McMorris and F.S. Roberts, p-competition graphs, Linear Algebra Appl. 217 (1995) 167–178. https://doi.org/10.1016/0024-3795(94)00060-Q

[12] F.S. Roberts and L. Sheng, Phylogeny graphs of arbitrary digraphs, in: Mathematical Hierarchies and Biology, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 37 (1997) 233–238. https://doi.org/10.1090/dimacs/037/15

[13] D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987) 269–280. https://doi.org/10.1016/0166-218X(87)90030-8

[14] S. Seager, Cyclic niche graphs and grids, Ars Combin. 49 (1998) 21–32.

[15] P. van't Hof and D. Paulusma, A new characterization of P6-free graphs, Discrete Appl. Math. 158 (2010) 731–740. https://doi.org/10.1016/j.dam.2008.08.025

[16] L. Volkmann, Multipartite tournaments: A survey, Discrete Appl. Math. 307 (2007) 3097–3129. https://doi.org/10.1016/j.disc.2007.03.053

[17] A. Yeo, Semicomplete multipartite digraphs, in: Classes of Directed Graphs, J. Bang-Jensen and G. Gutin (Ed(s)), (Springer Monogr. Math. 2018) 297–340. https://doi.org/10.1007/978-3-319-71840-8_7