| Abstract: | An acyclic digraph D =(V U X, <) induces a finite graph G =(V, E) if for all v,v′ if and only if a vertex of D dominates v and v′, or is dominated by v and v′. The niche number of an induced G is the cardinality of a smallest X for which some D induces G. Many induced graphs have niche number 0, 1, or 2, but it has been an open problem as to whether they can have larger niche numbers. We prove that there are induced graphs with arbitrarily large niche numbers. Explicit examples of graphs with niche numbers 3 and 4 are given. The smallest example uses 11 vertices. We note also that every induced graph with fewer than 8 vertices has niche number 0, 1, or 2. |
