2
$\begingroup$

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.

All help appreciated.

1 Answers 1

1

In that case, the answer must be 4 because I found such an example using Sage.

for g in graphs.nauty_geng("10 -c -d4"):     if g.is_regular() == True:         if g.is_clique() == False:             connect_diff = g.edge_connectivity() - g.vertex_connectivity()             if connect_diff >= 1:                 print g.graph6_string(), "has order", g.order(), "is", min(g.degree()), "regular and the difference is", connect_diff 

Explanation the nauty_geng generates all graphs of order 10 that are connected with minimum degree at least 4. I used this code starting at degree 4 just for completeness. The first graph at all with a difference at least 2 is of order 10. At order 10, there are two graphs with a difference of 2. One is 4-regular and one is 6-regular. The 4-regular graph is all you need, of course.

The graph is the graph with graph6 string = ICQrThiu?

It has edge connectivity 4 and vertex connectivity 2.

The vertices are 0 through 9 and the edges are given by Sage as:

[(0, 3, None), (0, 5, None), (0, 7, None), (0, 9, None), (1, 4, None), (1, 6, None), (1, 8, None), (1, 9, None), (2, 5, None), (2, 6, None), (2, 7, None), (2, 8, None), (3, 5, None), (3, 7, None), (3, 9, None), (4, 6, None), (4, 8, None), (4, 9, None), (5, 7, None), (6, 8, None)]

The basic shape of the graph is as follows. Take two 4-cliques and two other isolated vertices. For each 4-clique, take 2 vertices and connect them to one of the isolated vertices. Take other 2 vertices of the 4-clique and connect them to the other isolate vertex.