A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:

  1. for $e\in L$ we have $|e|\geq 2$;
  2. if $e_1\neq e_2 \in L$ then $|e_1\cap e_2|\leq 1$.

We set $X(\pi)=X$ and $L(\pi)=L$. The graph $G_\pi$ associated to a linear hypergraph $\pi$ is given by $G=(V,E)$ where $V = L$ and $E = \{\{e_1, e_2\} \subseteq L: e_1\neq e_2\text{ and } e_1\cap e_2\neq \emptyset\}$. It turns out that for any graph $G$ there is a linear hypergraph $\pi$ such that $G\cong G_\pi$. For any graph $G$ the we set $$\ell(G) := \text{min}\{|X(\pi)|:\pi \text{ is a linear hypergraph such that } G_{\pi} \cong G\}$$ and call this the linear intersection number of $G$. (For infinite graphs, this concept is boring: $\ell(G) = |V(G)|$ for infinite graphs.)

For any graph $G$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.

Does $\tau(G) \leq \ell(G)$ hold for all graphs $G$?

  • 3
    $\begingroup$ $V$ is used for too many things. $\endgroup$ – domotorp Jan 28 '15 at 14:24
  • $\begingroup$ That's right, thanks for pointing it out - I amended it.. $\endgroup$ – Dominic van der Zypen Jan 28 '15 at 15:35

Let $H$ be a graph on $n$ vertices, thought of as the hypergraph in the question. Then a vertex cover in $G_H$ is precisely a subgraph of $H$ that contains all but at most one edge at each vertex of $H$. Such a subgraph is obtained from $H$ by deleting a subgraph of maximum degree at most $1$, which contains at most $n/2$ edges. So any graph $H$ with more than $3n/2$ edges will provide a counterexample.


No, it might not hold. Let $\pi=K_{4,4}$, so $|X|=8$ and each $e\in L$ contains exactly two vertices. This implies that $\ell(G_\pi)\le 8$. But for each $x\in X$ we must select at least three of the four edges meeting there in any vertex cover of $G_\pi$, thus $\tau(G_\pi)\ge 3\cdot 8/2=12$.

  • $\begingroup$ Very nicely written - I would like to accept both Ben's and your answer! $\endgroup$ – Dominic van der Zypen Jan 29 '15 at 12:41
  • $\begingroup$ @Dominic: I guess he deserves it more as he spotted the mistake in my earlier attempt. $\endgroup$ – domotorp Jan 29 '15 at 15:45
  • $\begingroup$ OK - then I hope you don't mind if I accepted his answer (as I can only accept one answer). $\endgroup$ – Dominic van der Zypen Jan 29 '15 at 15:47

This answer is incorrect! As pointed out by Ben, I confused dominating set and vertex cover.

Yes, it is true. For every vertex $v$ of the hypergraph $\pi$, consider the edges of the graph $G$ that run between hyperedges that intersect in $v$. This will be a clique, which we can denote by $K_v$. We can select any vertex of the clique for each $v$, this gives a vertex cover of size at most "$\ell$".

The linearity seems not needed. It would imply, btw, that any two such cliques are edge-disjoint, that is, $K_v\cap K_u\cap E=\emptyset$. Therefore in this case the edgeset of the graph, $E$, is an edge-disjoint union of cliques.

  • 1
    $\begingroup$ This is certainly a dominating set (if you pick one hyperedge containing each hypervertex then every hyperedge meets some hyperedge in the set), but is it a vertex cover? For that you would need that for every intersecting pair of hyperedges, one of the pair is in the cover. Or have I misunderstood? $\endgroup$ – Ben Barber Jan 29 '15 at 11:27
  • $\begingroup$ Oops - I fell into the same trap... Thanks for the clarification! $\endgroup$ – Dominic van der Zypen Jan 29 '15 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.