0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Is it an edge or vertex cover? $\endgroup$
    – hbm
    May 26, 2012 at 16:08
  • 2
    $\begingroup$ And this seems like a statement, not a question... $\endgroup$
    – Igor Rivin
    May 26, 2012 at 16:34
  • $\begingroup$ 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... $\endgroup$ May 26, 2012 at 17:10
  • 2
    $\begingroup$ 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 ? $\endgroup$
    – Flávio
    May 26, 2012 at 22:49
  • 2
    $\begingroup$ At least you should edit your motivation from the comment above into the main body of the question. $\endgroup$ May 27, 2012 at 5:23

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
9
  • $\begingroup$ @Gerry, this argument won't work. Think of $K_{3,3}$. $\endgroup$ May 27, 2012 at 0:27
  • $\begingroup$ @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}$. $\endgroup$ May 27, 2012 at 5:32
  • $\begingroup$ 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 $\endgroup$ May 27, 2012 at 5:36
  • $\begingroup$ 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 $\endgroup$ May 27, 2012 at 5:41
  • $\begingroup$ 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 $\endgroup$ May 27, 2012 at 5:52
0
$\begingroup$

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, http://www.dharwadker.org/independent_set/fig2a.gif, has 6 vertices and a dominating set with three vertices. Is not This?

$\endgroup$
1
  • 1
    $\begingroup$ It also has a dominating set of size two. $\endgroup$ May 27, 2012 at 23:03
0
$\begingroup$

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

sage: g = graphs.HeawoodGraph()
sage: g.degree()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: g.order()
14
sage: g.vertex_cover()
[0, 2, 4, 6, 8, 10, 12]
$\endgroup$
2
  • $\begingroup$ Notice that for any regular graph, a vertex cover contains at least half of the vertices. $\endgroup$ May 29, 2012 at 8:21
  • $\begingroup$ ahahahah right ! And necessarily more if it is not bipartite :-) $\endgroup$ May 30, 2012 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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