Find a graph such that $\kappa(G) < \lambda(G) < \delta(G)$

Question

How would I go about constructing a graph that satisfies this inequality? I am new to graph theory so I'm not sure where to start. Note that:

$\kappa(G)$ is the vertex-connectivity of G, the size of the smallest separating set of G. (A separating set is a set of vertices of G whose deletion from the graph makes the graph become disconnected).

$\lambda(G)$ is the edge-connectivity of G, the size of the smallest disconnect set of G. (A disconnected set is a set of edges of G whose deletion from the graph makes the graph become disconnected).

$\delta(G)$ is the minimum degree of G (i.e. the degree of the vertex of G with the minimum degree).

Answer 1

Let $G$ be the following graph:

Then $\kappa(G)=1$ (remove its middle point), $\lambda(G)=2$ (remove $a$ and $b$) and $\delta(G)=3$.

Answer 2

Given integers $k,\ell,d$ with $1\le k\le\ell\le d$, here's how you can construct a graph $G$ with $\kappa(G)=k$, $\lambda(G)=\ell$, and $\delta(G)=d$.

Take five disjoint sets $V_1,V_2,V_3,V_4,V_5$ with $|V_1|=1$, $|V_2|=d$, $|V_3|=\ell$, $|V_4|=k$, $|V_5|=d$, and take a surjection $f:V_3\to V_4$.

The vertex set of $G$ is $V_1\cup V_2\cup V_3\cup V_4\cup V_5$.

For the edge set of $G$ take all edges $xy$ where $\{x,y\}\subseteq V_1\cup V_2$ or $\{x,y\}\subseteq V_2\cup V_3$ or $\{x,y\}\subseteq V_4\cup V_5$, and all edges $xy$ where $x\in V_3$ and $y=f(x)\in V_4$.

Note that $G$ can be disconnected by removing either the $k$ vertices in $V_4$ or the $\ell$ edges between $V_3$ and $V_4$, and that the vertex in $V_1$ has degree $d$. A little consideration will show that in fact $\kappa(G)=k$, $\lambda(G)=\ell$, and $\delta(G)=d$.

Answer 3

$\kappa(G)$ is the vertex-connectivity of G.

$\kappa'(G)$ is the edge-connectivity of G.

$\delta(G)$ is the minimum degree of G.

Reference

Answer 4

ɑ(G) is the vertex connectivity of G.

λ(G) is the edge connectivity of G.

δ(G) is the minimum degree of G.

Answer 5

watch out! mma GraphData hasn't implemented all graphs for vertex-number =8,9,10,11,12...

---

You can use Mathematica GraphData function to find the answer.

Here is an example.

func = {#, GraphData[#, "VertexConnectivity"], 
    GraphData[#, "EdgeConnectivity"], 
    GraphData[#, "MinimumVertexDegree"]} &;
selectedGraphs = 
 GraphData[All] // Map[func, #] & // 
  Select[#, (Part[#, 2] < Part[#, 3] && Part[#, 3] < Part[#, 4]) &] &

{{{"Quartic", {11, 1}}, 1, 2, 4}}   (* just find this, maybe exsits more*)


(*Note that mma GraphData hasn't implemented all graphs for vertex-number =8,9,10,11,12...*)

(*Plot the satisfied graphs*)
GraphicsGrid[
 Partition[GraphData /@ Map[Part[#, 1] &, selectedGraphs], UpTo[5]]]

For this graph,

• vertex-connectivity is $1$
• edge-connectivity is $2$
• minimum-vertex-degree is $4$