Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite natural expansion to that definition is to allow to take fractions of vertices. So similiraly, we can define $\tau ^ \star (H)$ to be the $\min {\{\Sigma_ {v\in V}{f(v)}\ \vert \ f:V \rightarrow \mathbb {R^+}, \ \forall e \in E(H):\ \Sigma _{v \in e}f(v) \geq 1\}} $.

Consider then the following $k$-uniform hypergraph: Take the cycle-graph $C_n$ and make every path with $k$ points in it (a $k$ lengthed segment on the cycle) an edge in the hypergraph. Take all these edges but leave one out (they are symmetrical, it doesn't matter which). We arrive at a $k$-uniform hypergraph $H_{n,k}$ with $n$ vertices and $n-1$ edges.

For every $n,k$ find $\tau^\star (H_{n,k}). $

Note 1: It's very easy to see that for the full $k$-cycle hypergraph (without removing 1 edge) we get $\tau^\star=n/k$ by taking $1/k$ for all vertices. Obviously by removing a single edge we wish to improve this bound.

Note 2: For $k=1$ (edges are singletons) we get $\tau^\star=n-1$ by taking 1 for every edge except the missing one.

Note 3: If $k\geq 2$ and $k\vert n$ then it's clear that we cannot get anything better than $n/k$ since we can always fully partition the cycle into $n/k$ edges and each edge must have weight of at least $1$.

Note 4: If $k=n-1$ then there exists an edge on which all edges meet. So we can easily get $\tau^\star=1$ by putting 1 on that vertex.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.