Welcome to MathOverflow

Question

0

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

edited May 27 at 5:34

Gerry Myerson
15.6k●1●47●87

asked May 26 at 15:43

Flávio
3

Is it an edge or vertex cover? – hbm May 26 at 16:08

2

And this seems like a statement, not a question... – Igor Rivin May 26 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 at 17:10

2

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 at 22:49

2

At least you should edit your motivation from the comment above into the main body of the question. – Gjergji Zaimi May 27 at 5:23

show 2 more comments

Gjergji Zaimi · Answer 1 · 2012-05-27 05:22:55Z UTC

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.

Gerry Myerson · Answer 2 · 2012-05-26 23:19:39Z UTC

1

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 at 23:19

Gerry Myerson
15.6k●1●47●87

	@Gerry, this argument won't work. Think of $K_{3,3}$. – Gjergji Zaimi May 27 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 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 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 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 at 5:52

show 4 more comments

Flávio · Answer 3 · 2012-05-27 21:15:27Z UTC

0

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?

answered May 27 at 21:15

Flávio
1

1

It also has a dominating set of size two. – Zack Wolske May 27 at 23:03

Nathann Cohen · Answer 4 · 2012-05-29 07:07:25Z UTC

0

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 at 7:07

Nathann Cohen
731●3●8

	Notice that for any regular graph, a vertex cover contains at least half of the vertices. – Gjergji Zaimi May 29 at 8:21
	ahahahah right ! And necessarily more if it is not bipartite :-) – Nathann Cohen May 30 at 7:00

Minimum covering in cubic graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.