Does a cubic graph with $2n$ vertices admit a minimal cover with $n-1$ vertices?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Is it an edge or vertex cover? $\endgroup$– hbmCommented May 26, 2012 at 16:08
-
2$\begingroup$ And this seems like a statement, not a question... $\endgroup$– Igor RivinCommented 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$– Vladimir DotsenkoCommented 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ávioCommented 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$– Gjergji ZaimiCommented May 27, 2012 at 5:23
|
Show 2 more comments
4 Answers
$\begingroup$
$\endgroup$
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.
answered May 27, 2012 at 5:22
$\begingroup$
$\endgroup$
9
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$.
answered May 26, 2012 at 23:19
-
$\begingroup$ @Gerry, this argument won't work. Think of $K_{3,3}$. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented May 27, 2012 at 5:52
$\begingroup$
$\endgroup$
1
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?
-
1$\begingroup$ It also has a dominating set of size two. $\endgroup$ Commented May 27, 2012 at 23:03
$\begingroup$
$\endgroup$
2
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]
answered May 29, 2012 at 7:07
-
$\begingroup$ Notice that for any regular graph, a vertex cover contains at least half of the vertices. $\endgroup$ Commented May 29, 2012 at 8:21
-
$\begingroup$ ahahahah right ! And necessarily more if it is not bipartite :-) $\endgroup$ Commented May 30, 2012 at 7:00