Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs*

NEW

Problem: For a fixed integer $j\ge1$, a $(2,j)$-digraph is a finite acyclic digraph with indegree at most $2$ and outdegree at most $j$. For such $D$, $C(D)$ joins two vertices with a common out-neighbor, and $P(D)$ joins two vertices if they are adjacent by an arc in either direction or have a common out-neighbor. Let $\kappa_{(2,j)}(G)$ be the least $q$ such that $G\cup I_q=C(D)$, and let $\phi_{(2,j)}(G)$ be the least $q$ such that $P(D)[V(G)]=G$ with $q$ added vertices.

The problem asks whether, for every $k\ge0$, there is a graph $G$ with

The nontrivial intended case is $j\ge2$; for $j=1$ the statement is false.

Result: For every fixed $j\ge2$, the answer is yes.

Let $c=k+1$, and let $G_c$ be the disjoint union of $c$ copies of $C_4$. Then $|V(G_c)|=|E(G_c)|=4c$.

First, $\kappa_{(2,j)}(G_c)=2$. In any competition realization, each edge needs a distinct witness, since indegree is at most $2$. In a topological order, the first two original vertices cannot witness an edge, so at most $4c-2$ original vertices can witness edges. Thus at least $4c-(4c-2)=2$ added vertices are necessary.

Conversely, two added vertices suffice: order the $C_4$’s consecutively, and for each cycle use its third and fourth vertices to witness its first two edges; use the first two vertices of the next cycle to witness its last two edges; for the final cycle use the two added vertices. All arcs go forward, indegrees are at most $2$, outdegrees are exactly $2$, and the competition graph is $G_c\cup I_2$.

Next, $\phi_{(2,j)}(G_c)=c$. One added vertex per $C_4$ suffices: orient three consecutive edges as a directed path and use the added vertex as a common child of the two endpoints of the missing fourth edge.

For the lower bound, consider any phylogeny realization. In each $C_4$-component, some added vertex must have two in-neighbors in that component. Otherwise, in the acyclic subdigraph induced by that $C_4$, take a sink $v$. Its two cycle-neighbors must both point to $v$, forcing them to share the out-neighbor $v$, hence making them adjacent in $P(D)$, a forbidden chord of $C_4$. One added vertex cannot serve two components because indegree is at most $2$. Hence at least $c$ added vertices are needed.

Therefore

If $j=1$, finite $\kappa_{(2,1)}$ forces $\Delta(G)\le1$, so $G$ is a matching plus isolated vertices; then $\phi_{(2,1)}(G)=0$, and the value is at most $1$. Thus $k\ge2$ is impossible.

Citation: Problem and notation: Y. Xiong, S. Zaw, Y. Zhu, “Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs,” Algebra Colloquium 27 (2020), 79–86. No prior resolution is used here.