Geodesic
Niche Hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 819-832.

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

If D = (V,A) is a digraph, its niche hypergraph Nℋ(D) = (V, ℰ) has the edge set ℰ = ℯ ⊆ V | |e| ≥ 2 ∧ ∃ v ∈ V : e = ND-(v) ∨ ℯ = ND+(v). Niche hypergraphs generalize the well-known niche graphs (see [11]) and are closely related to competition hypergraphs (see [40]) as well as double competition hypergraphs (see [33]). We present several properties of niche hypergraphs of acyclic digraphs.
Keywords: niche hypergraph, niche number 
@article{DMGT_2016_36_4_a3,
     author = {Garske, Christian and Sonntag, Martin and Teichert, Hanns-Martin},
     title = {Niche {Hypergraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {819--832},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a3/}
}
TY  - JOUR
AU  - Garske, Christian
AU  - Sonntag, Martin
AU  - Teichert, Hanns-Martin
TI  - Niche Hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 819
EP  - 832
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a3/
LA  - en
ID  - DMGT_2016_36_4_a3
ER  - 
%0 Journal Article
%A Garske, Christian
%A Sonntag, Martin
%A Teichert, Hanns-Martin
%T Niche Hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 819-832
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a3/
%G en
%F DMGT_2016_36_4_a3
Garske, Christian; Sonntag, Martin; Teichert, Hanns-Martin. Niche Hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 819-832. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a3/

[1] C.A. Anderson, Loop and cyclic niche graphs, Linear Algebra Appl. 217 (1995) 5-13. doi: 10.1016/0024-3795(94)00154-6

[2] C.A. Anderson, K.F. Jones, J.R. Lundgren and S. Seager, A suggestion for new niche numbers of graphs, in: Proc. 22-nd Southeastern Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge, USA (Util. Math. Publ. Inc., 1991) 23-32.

[3] C.A. Anderson, J.R. Lundgren, S. Bowser and C. Cable, Niche graphs and unit interval graphs, Congr. Numer. 93 (1993) 83-90.

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

[5] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).

[6] S. Bowser and C. Cable, Cliques and niche graphs, Congr. Numer. 76 (1990) 151-156.

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

[8] S. Bowser and C. Cable, The niche category of dense graphs, Ars Combin. 59 (2001) 289-297.

[9] S. Bowser and C. Cable, The niche category of sparse graphs, Ars Combin. 66 (2003) 179-192.

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

[11] 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

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

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

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

[15] W.V. Gehrlein and P.C. Fishburn, The smallest graphs with niche number three, Comput. Math. Appl. 27 (1994) 53-57. doi: 10.1016/0898-1221(94)90054-X

[16] W.V. Gehrlein and P.C. Fishburn, Niche number four, Comput. Math. Appl. 32 (1996) 51-54. doi: 10.1016/0898-1221(96)00176-9

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

[18] S.-J. Kim, S.-R. Kim and Y. Rho, On CCE graphs of doubly partial orders, Discrete Appl. Math. 155 (2007) 971-978. doi: 10.1016/j.dam.2006.09.013

[19] S.-R. Kim, J.Y. Lee, B. Park, W.J. Park and Y. Sano, The niche graphs of doubly partial orders, Congr. Numer. 195 (2009) 19-32.

[20] 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

[21] S.-R. Kim, J.Y. Lee, B. Park and Y. Sano, The competition hypergraphs of doubly partial orders, Discrete Appl. Math. 165 (2014) 185-191. doi: 10.1016/j.dam.2012.05.024

[22] S.-R. Kim, J.Y. Lee, 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

[23] 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

[24] 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

[25] J. Lu and Y. Wu, Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two, Appl. Math. Lett. 22 (2009) 841-845. doi: 10.1016/j.aml.2008.06.046

[26] J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs and niche graphs, in: F. Roberts (Ed(s)), Applications of Combinatorics and Graph Theory to the Biological and Social Sciences (IMA 17, Springer, New York, 1989) 221-243. doi: 10.1007/978-1-4684-6381-1 9

[27] 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

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

[29] 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

[30] 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.

[31] B. Park and S.-R. Kim, On Opsut’s conjecture for hypercompetition numbers of hypergraphs, Discrete Appl. Math. 160 (2012) 2286-2293. doi: 10.1016/j.dam.2012.05.009

[32] J. Park and Y. Sano, The niche graphs of interval orders, Discuss. Math. Graph Theory 34 (2014) 353-359. doi: 10.7151/dmgt.1741

[33] 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

[34] Y. Sano, The competition-common enemy graphs of digraphs satisfying conditions C(p) and C′(p), Congr. Numer. 202 (2010) 187-194.

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

[36] S. Seager, Niche graph properties of trees, in: Proc. 22-nd Southeastern Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge, USA (Util. Math. Publ. Inc., 1991) 149-155.

[37] S. Seager, Relaxations of niche graphs, Congr. Numer. 96 (1993) 205-214.

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

[39] 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

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

[41] M. Sonntag and H.-M. Teichert, Competition hypergraphs of digraphs with certain properties I. Strong connectedness, Discuss. Math. Graph Theory 28 (2008) 5-21. doi: 10.7151/dmgt.1388

[42] M. Sonntag and H.-M. Teichert, Competition hypergraphs of digraphs with certain properties II. Hamiltonicity, Discuss. Math. Graph Theory 28 (2008) 23-34. doi: 10.7151/dmgt.1389

[43] 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

[44] Y. Wu and J. Lu, Dimension-2 poset competition numbers and dimension-2 poset double competition numbers, Discrete Appl. Math. 158 (2010) 706-717. doi: 10.1016/j.dam.2009.12.001