A study on competition numbers of planar graphs

NEW

Problem: Reconstructed conjecture: every nonempty finite simple graph has an effective competition cover. Here an effective competition cover means a minimum edge clique cover $\mathcal C=\{C_1,\dots,C_{\theta_e(G)}\}$ by maximal cliques for which there is an acyclic loopless digraph $D$ with

$$C(D)=G\cup k(G)\text{ isolated vertices}$$

and distinct vertices $w_i$ such that the $w_i$'s are exactly the positive-indegree vertices of $D$, and every vertex of $C_i$ has an arc to $w_i$. This is the notion later called a competition-effective edge clique cover.

Result: The conjecture is false.

Let $G$ have vertices $a,b,c,d,e,f$ and edges

$$ab,ad,ae,af,bc,bd,bf,cd,ce.$$

First, $k(G)=1$. Since $G$ has no isolated vertex, $k(G)\ne0$, because every finite acyclic digraph has a vertex of outdegree $0$, which is isolated in its competition graph.

For $k(G)\le1$, add one vertex $x$ and define $D$ by

$$N_D^-(x)=\{a,b,f\},\quad N_D^-(f)=\{b,c,d\},\quad N_D^-(b)=\{c,e\},$$ $$N_D^-(c)=\{a,d\},\quad N_D^-(d)=\{a,e\},$$

with all other indegrees $0$. The order

$$e,a,d,c,b,f,x$$

is topological, so $D$ is acyclic. The nontrivial in-neighborhoods generate exactly the edges of $G$, and $x$ is isolated in $C(D)$. Hence $C(D)=G\cup\{x\}$, so $k(G)=1$.

The maximal cliques of $G$ are exactly

$$K_1=\{a,b,d\},\quad K_2=\{a,b,f\},\quad K_3=\{b,c,d\},\quad K_4=\{a,e\},\quad K_5=\{c,e\}.$$

Each has a private edge: respectively $ad,af,cd,ae,ce$. Thus every edge clique cover by maximal cliques must contain all five, and

$$\theta_e(G)=5.$$

Assume $G$ had an effective competition cover. Then the cover must be $\{K_1,\dots,K_5\}$. There is only one added vertex $x$, so at most one clique can have non-original sink.

Lemma: if a subfamily $\mathcal F$ of cliques has original sinks $s(K)$, then for every nonempty $\mathcal H\subseteq\mathcal F$, some $K\in\mathcal H$ has

$$s(K)\notin \bigcup_{L\in\mathcal H}L.$$

Indeed, define an auxiliary digraph on $\mathcal H$ by $K\to L$ if $s(K)\in L$. A directed cycle would give a directed cycle among the sinks in $D$. Hence the auxiliary digraph is acyclic and has a vertex of outdegree $0$.

If all five clique sinks are original, the lemma requires an original vertex outside $\bigcup_iK_i=V(G)$, impossible. Hence $x$ sinks one clique. If $x$ does not sink $K_2=\{a,b,f\}$, the remaining four cliques still cover all of $V(G)$, again impossible. Thus $x$ must sink $K_2$.

Then the original-sink cliques are

$$K_1,K_3,K_4,K_5,$$

whose union is $V(G)\setminus\{f\}$. By the lemma, one of them must have sink $f$. Remove that clique. The remaining three still have union $V(G)\setminus\{f\}$, so the lemma forces another distinct clique also to have sink $f$, contradicting distinctness of sinks.

Therefore $G$ has no effective competition cover.

Verification audit: $G$ is finite, simple, connected, and has edges; $k(G)=1$ and $\theta_e(G)=5$ were proved directly; the only possible minimum maximal edge clique cover was checked; the contradiction uses exactly the effective-cover definition and no extra hypothesis.

Citation: Definitions/conjecture source: Jihoon Choi, Soogang Eoh, Suh-Ryung Kim, “A study on competition numbers of graphs in the aspect of primary predator index,” arXiv:1602.04623. The counterexample above is self-contained.