Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs*

NEW

Problem: For finite simple connected graphs, let $\kappa(G)$ be the competition number: the least $r$ such that $G\cup rK_1$ is the competition graph of an acyclic digraph. Let $\varphi(G)$ be the phylogeny number: the least number of extra vertices in an acyclic digraph $D$ with $P(D)[V(G)]=G$, where $xy\in E(P(D))$ iff $x\to y$, $y\to x$, or $x,y$ have a common out-neighbor. The reconstructed question is:

$$\forall k\in \mathbb N_0\ \exists\text{ connected }G:\quad \varphi(G)-\kappa(G)+1=k .$$

Result: The statement is true.

For $k=0$, take $G=K_2$. Then $\varphi(G)=0$ by orienting its edge, and $\kappa(G)=1$.

For $k\ge1$, construct $G_k$ from $k$ gadgets. Gadget $i$ has vertices

$$a_i,b_i,c_i,d_i,x_i,y_i$$

and edges

$$a_ix_i,\ x_ib_i,\ b_iy_i,\ y_ia_i,\ a_ic_i,\ c_id_i,\ d_ia_i.$$

Thus it is a $4$-cycle $a_ix_ib_iy_ia_i$ with a triangle $a_ic_id_ia_i$ attached at $a_i$. Connect consecutive gadgets by bridges $d_i a_{i+1}$.

First, $\kappa(G_k)=1$. Since $G_k$ is connected and has no isolated vertices, $\kappa(G_k)\ne0$, because every finite acyclic digraph has a sink, isolated in its competition graph. For the upper bound, add one new sink $z$, order vertices as

$$a_i,x_i,b_i,y_i,c_i,d_i\quad (i=1,\dots,k),\quad z,$$

and prescribe nontrivial in-neighborhoods

$$N^-(b_i)=\{a_i,x_i\},\quad N^-(y_i)=\{x_i,b_i\},$$ $$N^-(c_i)=\{a_i,y_i\},\quad N^-(d_i)=\{b_i,y_i\},$$ $$N^-(a_{i+1})=\{a_i,c_i,d_i\},\quad N^-(x_{i+1})=\{d_i,a_{i+1}\}\quad (i<k),$$

and

$$N^-(z)=\{a_k,c_k,d_k\}.$$

All arcs go forward, so the digraph is acyclic. The parent sets generate exactly the listed edges of $G_k$, and $z$ is isolated in the competition graph. Hence $\kappa(G_k)=1$.

Next, $\varphi(G_k)=k$. For the upper bound, delete the $k$ edges $a_i y_i$. The remaining graph is chordal: each gadget becomes a triangle with a path attached, and the bridges create no cycle. Every chordal graph is a phylogeny graph of an acyclic digraph with no extra vertices. Add one new sink $w_i$ with arcs $a_i\to w_i$, $y_i\to w_i$ for each $i$. This restores exactly the deleted edges, so $\varphi(G_k)\le k$.

For the lower bound, let $Q_i=a_ix_ib_iy_ia_i$. In $G_k$, no original vertex outside $Q_i$ is adjacent to both endpoints of any edge of $Q_i$. Thus an edge of $Q_i$ can be realized in a phylogeny digraph only as an arc between its endpoints or by a common extra out-neighbor. If no extra vertex realizes an edge of $Q_i$, then all four edges of $Q_i$ must be arcs. Any acyclic orientation of a cycle has a sink on the cycle, whose two cycle-neighbors then share that sink as a common out-neighbor, forcing a forbidden diagonal of $Q_i$. Contradiction. Hence each $Q_i$ needs an extra vertex.

The cycles $Q_i$ and $Q_j$ are anticomplete for $i\ne j$, so one extra vertex cannot realize edges in two different $Q_i$’s; otherwise it would create cross-edges between them. Therefore $\varphi(G_k)\ge k$. Hence $\varphi(G_k)=k$.

Thus, for $k\ge1$,

$$\varphi(G_k)-\kappa(G_k)+1=k-1+1=k.$$

Citation: No prior resolution is used. Source problem: Y. Xiong, S. Zaw, and Y. Zhu, “Competition Numbers and Phylogeny Numbers of Connected Graphs and Hypergraphs,” Algebra Colloquium 27 (2020), Problem 2(i).