Welcome to MathOverflow

Question

0

1

Hello everyone. I'm really struggling with this question. All help appreciated.

Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ(G) + 2

I know it's not 1,2,3-regular since κ(G) = λ(G) for those graphs.

flag	asked Apr 9 2012 at 7:46 janvdl 11

This is a homework question: google.com/… – domotorp Apr 9 2012 at 8:11

Actually it's an exercise from Chartrand & Lesniak Ex2.4 Q.16, and it's not homework. – janvdl Apr 9 2012 at 8:32

2

I'd suggest you put such question on math.stackexchange.com . – Jernej Apr 9 2012 at 9:14

Just consider all the possibilities, there are very few. – Brendan McKay Apr 9 2012 at 14:56

w g · Answer 1 · 2012-04-19 23:38:08Z UTC

Take tow disjoint copies of the complete graph on 5 vertices. Pick a vertex on each of the copy and split into tow vertices of degree 2. Match the the degree 2 vertices of both copies the identify them to get 4-regular, 4-egde-connected, and 2-vertex-connected graph.

Graph Theory - Connectivity of r-regular graphs

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

1 Answer

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.