Construct a simple graph $G$ with $\kappa (G) = 1439$, $\kappa '(G) = 2018$, and $\delta (G)= 5778$ and prove that it has these properties.

Not sure how to approach this. I have a few ways of finding restrictions on such a graph. e.g. a minimal edge cut $[S, \bar{S}]$ satisfies $$2018=|[S, \bar{S}]|=\sum_{v\in S} d(v) -2e(G[S])\geq 5778 |S|-2e(G[S])$$ But I can't see how to actually "construct" such a graph.

Clarification: $\kappa (G)$ is the vertex connectivity of $G$, $\kappa' (G)$ is the edge-connectivity of $G$, $\delta (G)$ is the minimal vertex degree of $G$.

  • 3
    $\begingroup$ What are $\kappa$, $\kappa'$ and $\delta$? $\endgroup$ – user251573 Aug 24 '18 at 13:59
  • $\begingroup$ @Akkert see edit. I thought these were standard symbols (I'm using Douglas B. West's Introduction to Graph Theory) $\endgroup$ – Bary12 Aug 24 '18 at 14:28

Your Answer

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

Browse other questions tagged or ask your own question.