I am working on a computing mini-project and I am stuck because of the following problem:
"Given a number of nodes N and a connectivity k such that $N > k + 1$, is it always possible to construct a connected graph in which each node has exactly k undirected links to other nodes?"
If it's not always possible, what are the restrictions? Can you think of any algorithm I could use to create a NxN Hermitian connectivity matrix in which I store a zero if the nodes are not connected and a one if they are connected? (N.B. The matrix has to be Hermitian because the links are undirected.)
I'm really stuck and the deadline is approaching, so any help would be very much appreciated.
Best Answer
Yes it is possible to construct a $k$-regular graph that is $k$-connected, where the number $n$ of vertices is arbitrarily large. There are a few ways to go about doing this. This is a sketch of one way.
For $k$ even the number $n$ of vertices may be even or odd. Let $G$ be a graph where the vertex-set is $\mathbb{Z}/n\mathbb{Z}= \{0,1,\ldots, n-1 \}$, where $i$ is adjacent to each $j$ s.t. either $j-i$ or $i-j$ is $\left\{1, \ldots, \frac{k}{2}\right\}$ where all arithmetic is done mod $n$.
So for $k=2$ the graph $G$ is a cycle on $n$ vertices.
For $k$ odd the number $n$ of vertices must be even. Let $G$ be a graph where the vertex-set is $\mathbb{Z}/n\mathbb{Z}$, where $i$ is adjacent to each $j$ s.t. either $i-j \in \left\{1, \ldots, \left\lfloor \frac{k}{2} \right\rfloor \right\}$, or $j=i + \frac{n}{2}$ where all arithmetic is done mod $n$.