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:

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

and edges

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

and prescribe nontrivial in-neighborhoods

and

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$,

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).