Since $\delta(G) \ge \kappa(G) \ge k$, we can see that: $$ |E(G)| \ge \frac{n \delta(G)}{2} \ge \frac{nk}{2} $$ Is this the best bound possible?

For $k = 4$, the answer to another question suggests that a cycle with an extra edge connecting each vertex with the vertex two away clockwise is a $4$-connected graph with $\frac{4n}{2} = 2n$ edges. It seems you can generalize that example to all $k$ even. Is there an example of a $k$-connected graph with $\frac{nk}{2}$ edges when $k$ is odd?

  • $\begingroup$ The complete bipartite graph $K_{k,k}$ comes to mind, although obviously this requires $n=2k$. For larger $n$, maybe there is some way of increasing the part sizes while maintaining the $k$-connectivity. $\endgroup$ – Joffan Mar 13 '18 at 0:07

The Harary graphs $H_{k,n}$ are the generalization of your construction to arbitrary $n$ and $k$.

For all $n$ and $k$, we place $n$ vertices around a circle, and then:

  • Join each vertex to the $\lfloor \frac k2 \rfloor$ vertices closest to it in either direction.
  • If $k$ is odd and $n$ is even, join each vertex to the vertex directly opposite it in the circle.
  • If $k$ is odd and $n$ is odd, number the vertices $0, 1, \dots, n-1$, and connect vertex $i$ to vertex $i + \frac{n-1}{2}$ for $0 \le i \le \frac{n-1}{2}$.

The result is a $k$-connected graph on $n$ vertices with the minimum possible number of edges: $\lceil \frac{kn}{2} \rceil$.


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.