Reducing from Hamiltonian Cycle problem to the Graph Wheel problem
We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$. $G$ has a Hamiltonian cycle if and only if $G'$ has a $W_{n+1}$. It is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W_{n+1}$ wheel (just set $v$ as a center). On the other hand, if $G'$ has a $W_{n+1}$ then there are two possibility:


$v$ is the center of $W_{n+1} \rightarrow G $ has a Hamiltonian cycle.
Another vertex $u$ is the center of $W_{n+1}$ in $G'$. So both $deg(u) = deg(v) = n$. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.


P.S1: By $W_n$ I mean the wheel with $n$ vertex.

P.S2: In this proof we say if we fix $k=n+1$ (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case $k$ is as input parameter.