Independence number of a graph based on $k$-permutations of $n$
Solution 1:
Such graphs are called arrangement graphs $A_{n,k}$. Your intuition about the independence number is correct. The independence number of $A_{n,k}$ is $\frac{n!}{(n-k+1)!}$. See corollary 3.6 of the following paper:
Liu et al., A Note of Independent Number and Domination Number of $Q_{n,k,m}$-Graph, Parallel Processing Letters (2019).
Note: In that paper, they prove this result for the superclass of $Q_{n,k,m}$ graphs which may be of interest to you if you are working on networks.