×

Niche hypergraphs. (English) Zbl 1350.05112

Summary: If \(D = (V,A)\) is a digraph, its niche hypergraph \(N\mathcal{H}(D) = (V, E)\) has the edge set \(\mathcal{E}= \{e\subseteq V \mid |e|\geq 2 \wedge \exists v\in V : e = N^-_D(v)\vee e = N^+_D(v)\}\). Niche hypergraphs generalize the well-known niche graphs and are closely related to competition hypergraphs as well as double competition hypergraphs. We present several properties of niche hypergraphs of acyclic digraphs.

MSC:

05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C.A. Anderson, Loop and cyclic niche graphs, Linear Algebra Appl. 217 (1995) 5-13. doi:; · Zbl 0828.05030 · 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.; · Zbl 0765.05054
[3] C.A. Anderson, J.R. Lundgren, S. Bowser and C. Cable, Niche graphs and unit interval graphs, Congr. Numer. 93 (1993) 83-90.; · Zbl 0809.05054
[4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2001).; · Zbl 0958.05002
[5] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973).; · Zbl 0254.05101
[6] S. Bowser and C. Cable, Cliques and niche graphs, Congr. Numer. 76 (1990) 151-156.; · Zbl 0862.05066
[7] S. Bowser and C. Cable, Some recent results on niche graphs, Discrete Appl. Math. 30 (1991) 101-108. doi:; · Zbl 0713.05032 · 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.; · Zbl 1066.05069
[9] S. Bowser and C. Cable, The niche category of sparse graphs, Ars Combin. 66 (2003) 179-192.; · Zbl 1073.05565
[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:; · Zbl 0942.05027 · 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:; · Zbl 0677.05039 · 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:; · Zbl 1241.92071 · doi:10.1051/mmnp/20116602
[14] P.C. Fishburn and W.V. Gehrlein, Niche numbers, J. Graph Theory 16 (1992) 131-139. doi:; · Zbl 0758.05092 · 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:; · Zbl 0804.05070 · 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:; · Zbl 0871.05038 · 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:; · Zbl 0789.05041 · 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:; · Zbl 1118.05041 · 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.; · Zbl 1218.05061
[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:; · Zbl 1287.05070 · 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:; · Zbl 1288.05187 · 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:; · Zbl 1304.05116 · 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:; · Zbl 1255.05088 · 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:; · Zbl 1252.05076 · 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:; · Zbl 1185.05120 · 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:; · Zbl 0701.92023 · doi:10.1007/978-1-4684-6381-1
[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:; · Zbl 1292.05197 · doi:10.1137/110856277
[28] B. Park and Y. Sano, On the hypercompetition numbers of hypergraphs, Ars Combin. 100 (2011) 151-159.; · Zbl 1265.05449
[29] B. Park and Y. Sano, The competition numbers of ternary Hamming graphs, Appl. Math. Lett. 24 (2011) 1608-1613. doi:; · Zbl 1219.05064 · 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.; · Zbl 1283.05240
[31] B. Park and S.-R. Kim, On Opsut’s conjecture for hypercompetition numbers of hypergraphs, Discrete Appl. Math. 160 (2012) 2286-2293. doi:; · Zbl 1252.05156 · 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:; · Zbl 1290.05124 · 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:; · Zbl 1320.05050 · 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.; · Zbl 1231.05114
[35] Y. Sano, On the hypercompetition numbers of hypergraphs with maximum degree at most two, Discuss. Math. Graph Theory 35 (2015) 595-598. doi:; · Zbl 1317.05078 · 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.; · Zbl 0765.05040
[37] S. Seager, Relaxations of niche graphs, Congr. Numer. 96 (1993) 205-214.; · Zbl 0806.05036
[38] S. Seager, Cyclic niche graphs and grids, Ars Combin. 49 (1998) 21-32.; · Zbl 0963.05115
[39] D.D. Scott, The competition-common enemy graph of a digraph, Discrete Appl. Math. 17 (1987) 269-280. doi:; · Zbl 0609.05038 · 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:; · Zbl 1056.05103 · 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:; · Zbl 1166.05006 · 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:; · Zbl 1166.05007 · 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:; · Zbl 1197.05101 · 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:; · Zbl 1225.05188 · doi:10.1016/j.dam.2009.12.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.