MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does a cubic graph with $2n$ vertices admit a minimal cover with $n-1$ vertices?

share|cite|improve this question
Is it an edge or vertex cover? – hbm May 26 '12 at 16:08
And this seems like a statement, not a question... – Igor Rivin May 26 '12 at 16:34
The way it is stated, it's not a real question. Voting to close. Once you formulate it, don't forget to convince us it's not your homework from a course in combinatorics... – Vladimir Dotsenko May 26 '12 at 17:10
Consider a nodal curve $ C $ with 2n components where each component intersects the curve complementary to it on three points. We can interpret each component of the curve $C$ as a vertex and each node how a edge, obtaining thus, a graph called the dual graph of the curve $ C $. My question is if I can chose $n-1$ components (vertices) so that each one these components (vetices) intersect at least one component among the other $n+1$ components. This is not a problem for minimal covering of graphs ? – Flávio May 26 '12 at 22:49
At least you should edit your motivation from the comment above into the main body of the question. – Gjergji Zaimi May 27 '12 at 5:23

A subset of vertices $S$ in a graph $G$ is called a dominating set if every vertex in $G$ is in $S$ or is connected to a vertex in $S$. The size of the smallest dominating set in a graph is called the domination number of $G$.

Even though your question asks about a minimum (vertex/edge) covering, what you seem to be interested in is the dominating number of a cubic graph. Not only does the domination number satisfy the bound in your question, but it can be improved further. Bruce Reed showed in "Paths, stars, and the number three", Combin. Probab. Comput. 5 (1996) 277--295, that every cubic graph has its domination number bounded by $3|V|/8$, where $|V|$ is the number of vertices in your graph. The bound is achieved for some graphs on 8 vertices. This bound has been more recently improved on by Kostochka and Stodolsky. I believe the conjectured best bound is $5|V|/14$, but it is not known if infinitely many graphs achieve it.

share|cite|improve this answer

Pick any vertex. It is adjacent to three other vertices. Now repeatedly pick an edge joining two vertices, call them $x$ and $y$, such that $y$ has not yet been accounted for, and choose $x$. Each such choice adds one more to the vertices accounted for. When you've exhausted the graph, you've picked $n-1$ vertices such that each of the other $n+1$ vertices is adjacent to at least one of the $n-1$.

share|cite|improve this answer
@Gerry, this argument won't work. Think of $K_{3,3}$. – Gjergji Zaimi May 27 '12 at 0:27
@Gjergji, let the vertices of $K_{3,3}$ be $a,b,c,1,2,3$, with letters adjacent to numbers. Pick $a$. It is adjacent to $1,2,3$. Now there's an edge joining $b$ and $1$, and $b$ has not yet been accounted for, so choose $1$. Now we've accounted for everything, so we have picked 2 vertices ($a$ and $1$) such that each of the other 4 vertices is adjacent to at least one of the 2 we picked. It's possible that my argument doesn't work, but I think it works for $K_{3,3}$. – Gerry Myerson May 27 '12 at 5:32
As I understand Gerry's argument, it does work for K_3,3. I don't know about other cubic graphs. Gerhard "Looks Like It Works Though" Paseman, 2012.05.26 – Gerhard Paseman May 27 '12 at 5:36
Of course, his argument establishes an upper bound, not an exact number. To get exactly n-1 you have to be carefully clumsy, or perhaps I mean clumsily careful. Gerhard "Still Thinks It Could Work" Paseman, 2012.05.26 – Gerhard Paseman May 27 '12 at 5:41
Also, there is the issue of minimality. Until we have a clear idea of what is wanted, I would say the answer is no, n-1 is not guaranteed for 2n vertices. Gerhard "Waiting For The Fine Print" Paseman, 2012.05.26 – Gerhard Paseman May 27 '12 at 5:52

Dear Gjergji Zaimi, thank you for your reply but I think there is something wrong with this value $ 3 | V | / $ 8 because the following cubic graph,, has 6 vertices and a dominating set with three vertices. Is not This?

share|cite|improve this answer
It also has a dominating set of size two. – Zack Wolske May 27 '12 at 23:03

Looks wrong. The Heawood graph is 3-regular on 14 vertices and its vertex cover is 7.

sage: g = graphs.HeawoodGraph()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: g.order()
sage: g.vertex_cover()
[0, 2, 4, 6, 8, 10, 12]
share|cite|improve this answer
Notice that for any regular graph, a vertex cover contains at least half of the vertices. – Gjergji Zaimi May 29 '12 at 8:21
ahahahah right ! And necessarily more if it is not bipartite :-) – Nathann Cohen May 30 '12 at 7:00

Your Answer


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

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