Can the equivalence number (equivalently, product dimension) of an $n$-vertex graph equal $n$?

Let $G$ be a finite simple graph. An equivalence graph is a graph whose connected components are cliques (equivalently, a disjoint union of complete graphs, a cluster graph). Define the equivalence number $eq(G)$ as the minimum number of equivalence graphs whose union covers $E(G)$.

I am interested in the maximum possible value of $eq(G)$ among graphs on $n$ vertices. In particular, is it possible that

$ eq(G)=n? $

There is a useful connection with product dimension. If $\operatorname{pdim}(H)$ denotes the product dimension of $H$, then

$ eq(G)=\operatorname{pdim}(\overline G). $

Thus the question is equivalent to asking whether there exists an $n$-vertex graph $H$ such that

$ \operatorname{pdim}(H)=n. $

There is also an elementary upper bound

$ eq(G)\leq \chi'(G)\leq \Delta(G)+1\leq n, $

because every matching is an equivalence graph and Vizing's theorem gives $\chi'(G)\leq\Delta(G)+1$.

Consequently, if $eq(G)=n$, then necessarily

$ \chi'(G)=n, $

and hence

$ \Delta(G)=n-1. $

Thus $G$ must have a universal vertex.

This leads to the following more specific question:

Question. Does every $n$-vertex graph satisfy $eq(G)\leq n-1$?

The value $eq(G)=n-1$ is attained for the star $K_{1,n}$.

Only for an $n$-vertex graph $G$ with a universal vertex, $eq(G)=n$ can hold. A natural attempted proof is to let $v$ be a universal vertex, label the other vertices $v_1,\ldots,v_{n-1}$, and construct $n-1$ equivalence graphs $F_1,\ldots,F_{n-1}$, where $vv_i\in E(F_i)$. The remaining edges would then have to be assigned to the $F_i s in such a way that the edges assigned to each $F_i$ form a disjoint union of cliques. I have not been able to prove that such an assignment always exists.

添加评论
点赞收藏
点踩分享查看原文
评论
?
参与讨论