Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs*

NEW

Problem: In the cited paper, an $(i,j)$-digraph means an acyclic digraph with indegree at most $i$ and outdegree at most $j$. For a graph $G$, $\kappa_{(i,j)}(G)$ and $\phi_{(i,j)}(G)$ are the least numbers of extra vertices in an acyclic $(i,j)$-digraph $D$ such that $G$ is an induced subgraph of $C(D)$, respectively of $P(D)=C(D^\circ)$.

Reconstructed Problem 2(iv): for a fixed positive integer $j$, is it true that for every $k\ge 0$ there is a connected graph $G$ with

Result: No. In fact, for every positive integer $j$ and every connected graph $G$ with at least two vertices and finite $\kappa_{(2,j)}(G)$,

Thus $k=2$, for example, is impossible.

Proof. Let $G$ be connected, $|V(G)|=n\ge2$, $|E(G)|=m$, and suppose $G$ is induced in $C(D)$ for an acyclic $(2,j)$-digraph $D$. Since every vertex of $D$ has indegree at most $2$, a single out-neighbor can witness at most one edge of $G$. Hence each edge of $G$ needs a distinct witness vertex. Moreover, in any topological ordering of $D$, an original vertex of $G$ can witness an edge of $G$ only if two original vertices precede it, so at most $n-2$ original vertices can be witnesses. Therefore at least

extra vertices are necessary:

Also, finite $\kappa_{(2,j)}(G)$ implies $\Delta(G)\le j$, because each incident edge of a vertex requires a distinct outgoing arc.

Now choose a spanning tree $T$ of $G$, orient $T$ away from a root, and for each non-tree edge $uv\in E(G)\setminus E(T)$, add one new sink $x_{uv}$ with arcs $u\to x_{uv}$ and $v\to x_{uv}$. This acyclic digraph has indegree at most $2$, and each original vertex has outdegree at most $\deg_G(v)\le j$. Its phylogeny graph induces exactly $G$: tree edges appear as arcs, and non-tree edges appear by their added common child. Thus

Combining (1) and (2),

So no connected graph with at least two vertices can realize any positive value. The one-vertex graph has $\phi_{(2,j)}=\kappa_{(2,j)}=0$, giving value $1$, and $K_2$ gives value $0$. Hence the proposed “every nonnegative integer” statement is false.

Citation: Problem and definitions: Y. Xiong, S. Zaw, Y. Zhu, “Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs,” Algebra Colloquium 27 (2020), 79–86. The disproof above is self-contained.