Niche Hypergraphs of Products of Digraphs

Sonntag, Martin ; Teichert, Hanns-Martin

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 279-295.

Résumé

If D = (V, A) is a digraph, its niche hypergraph N ℋ (D) = (V, ℰ ) has the edge set ℰ = { e ⊆ V | |e| ≤ 2 ∃ υ ∈ V : e = N_D^− (υ) e=N_D^+ (υ) }. Niche hypergraphs generalize the well-known niche graphs and are closely related to competition hypergraphs as well as common enemy hypergraphs. For several products D_1 ∘ D_2 of digraphs D_1 and D_2, we investigate the relations between the niche hypergraphs of the factors D_1, D_2 and the niche hypergraph of their product D_1 ∘ D_2.

Détail

Keywords: niche hypergraph, product of digraphs, competition hypergraph

Bibliographie

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2001).

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

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

[4] M. Cozzens, Food webs, competition graphs and habitat formation, Math. Model. Nat. Phenom. 6 (2011) 22–38. doi:10.1051/mmnp/20116602

[5] C. Garske, M. Sonntag and H.-M. Teichert, Niche hypergraphs, Discuss. Math. Graph Theory 36 (2016) 819–832. doi:10.7151/dmgt.1893

[6] S.-R. Kim, The competition number and its variants, in: Quo Vadis, Graph Theory?, Ed(s) J. Gimbel, J.W. Kennedy and L.V. Quintas (Ann. Discrete Math. 55, North Holland, Amsterdam, 1993). doi:10.1016/S0167-5060(08)70396-0

[7] S.-R. Kim, B. Park and Y. Sano, The competition number of the complement of a cycle, Discrete Appl. Math. 161 (2013) 1755–1760. doi:10.1016/j.dam.2011.10.034

[8] S.-R. Kim, B. Park and Y. Sano, A generalization of Opsut ’ s result on the competition numbers of line graphs, Discrete Appl. Math. 181 (2015) 152–159. doi:10.1016/j.dam.2014.10.014

[9] J. Kuhl, Transversals and competition numbers of complete multipartite graphs, Discrete Appl. Math. 161 (2013) 435–440. doi:10.1016/j.dam.2012.09.012

[10] B.-J. Li and G.J. Chang, Competition numbers of complete r-partite graphs, Discrete Appl. Math. 160 (2012) 2271–2276. doi:10.1016/j.dam.2012.05.005

[11] J.R. Lundgren, Food webs, competition graphs, competition—common enemy graphs and niche graphs, in: Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, Ed(s) F. Roberts (IMA 17, Springer, New York 1989) 221–243.

[12] B.D. McKey, P. Schweitzer and P. Schweitzer, Competition numbers, quasi line graphs and holes, SIAM J. Discrete Math. 28 (2014) 77–91. doi:10.1137/110856277

[13] B. Park and Y. Sano, On the hypercompetition numbers of hypergraphs, Ars Combin. 100 (2011) 151–159.

[14] B. Park and Y. Sano, The competition numbers of ternary Hamming graphs, Appl. Math. Lett. 24 (2011) 1608–1613. doi:10.1016/j.aml.2011.04.012

[15] B. Park and Y. Sano, The competition number of a generalized line graph is at most two, Discrete Math. Theor. Comput. Sci. 14 (2012) 1–10.

[16] J. Park and Y. Sano, The double competition hypergraph of a digraph, Discrete Appl. Math. 195 (2015) 110–113. doi:10.1016/j.dam.2014.04.001

[17] Y. Sano, On hypercompetition numbers of hypergraphs with maximum degree of at most two, Discuss. Math. Graph Theory 35 (2015) 595–598. doi:10.7151/dmgt.1826

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

[19] M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324–329. doi:10.1016/j.dam.2004.02.010

[20] M. Sonntag and H.-M. Teichert, Competition hypergraphs of products of digraphs, Graphs Combin. 25 (2009) 611–624. doi:10.1007/s00373-005-0868-9

[21] M. Sonntag and H.-M. Teichert, Products of digraphs and their competition graphs, Discuss. Math. Graph Theory 36 (2016) 43–58. doi:10.7151/dmgt.1851