Article in volume
Authors:
Title:
The niche graphs of multipartite tournaments
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1123-1146
Received: 2020-11-23 , Revised: 2021-06-29 , Accepted: 2021-07-01 , Available online: 2021-07-21 , https://doi.org/10.7151/dmgt.2424
Abstract:
The niche graph of a digraph $D$ has $V(D)$ as the vertex set and an edge
$uv$ if and only if $(u,w) \in A(D)$ and $(v,w) \in A(D)$, or $(w,u) \in A(D)$
and $(w,v) \in A(D)$ for some $w \in 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 \ge 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 \ge 3$. We show that the niche graph
of a $k$-partite tournament has at most three components if $k \ge 3$ and is
connected if $k \ge 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
References:
- 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 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982).
- 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 - 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:4<319::AID-JGT7>3.0.CO;2-S - 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 - 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 - J.E. Cohen, Interval graphs and food webs: a finding and a problem (RAND Corporation Document 17696-PR, Santa Monica, CA, 1968).
- 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 - 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 - P.C. Fishburn and W.V. Gehrlein, Niche numbers, J. Graph Theory 16 (1992) 131–139.
https://doi.org/10.1002/jgt.3190160204 - 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 - 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 - 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 - S. Seager, Cyclic niche graphs and grids, Ars Combin. 49 (1998) 21–32.
- P. van't Hof and D. Paulusma, A new characterization of $P_6$-free graphs, Discrete Appl. Math. 158 (2010) 731–740.
https://doi.org/10.1016/j.dam.2008.08.025 - L. Volkmann, Multipartite tournaments: A survey, Discrete Appl. Math. 307 (2007) 3097–3129.
https://doi.org/10.1016/j.disc.2007.03.053 - 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
Close