1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Could you please define $\kappa(G),\lambda(G)$ and $\delta(G)$ for us non-graph theorists around here? :) $\endgroup$ – Luiz Cordeiro Oct 11 '19 at 1:32
  • $\begingroup$ @LuizCordeiro Updated. $\endgroup$ – A.B Oct 11 '19 at 2:15
  • $\begingroup$ What is $\delta(G)$? For the first inequality, consider two large, disjoint cliques, and add a new node with an edge to every node in the two cliques. Then removing that new node disconnects the graph, but you'd need to remove many edges to disconnect the graph. $\endgroup$ – J.G Oct 11 '19 at 2:40
1
$\begingroup$

Let $G$ be the following graph:

enter image description here

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Perfect, thank you so much! If I may ask, how do you think about this when you are trying to come up with a graph? $\endgroup$ – A.B Oct 11 '19 at 3:06
  • $\begingroup$ Well, $\kappa(G)$ should be small, so I'll just take two separated graphs (like the squares which form $G$ in the answer) joined by a single point. Removing that point will disconnect the graph. Now $\lambda(G)$ should also be small-ish. Since removing the middle point makes the graph disconnected, removing the edges around it will also do so. We just need to ensure there are at least two edges "in each direction" to make $\lambda(G)>\kappa(G)$. Two squares do fine (two triangles would also work). I then added the middle points in the squares to make $\delta(G)$ larger. $\endgroup$ – Luiz Cordeiro Oct 11 '19 at 3:14
  • $\begingroup$ @K.B. So in some way, we just start with one of the desired properties ($\kappa$ small), and then modify the result step-by-step to have the extra properties ($\lambda$ larger than $\kappa$, but not too much, then $\delta$ large). $\endgroup$ – Luiz Cordeiro Oct 11 '19 at 3:15
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.