$S_k \in Aut(G)$, $deg(G) < (k-1)$?

Question

Given the symmetric group on $k$ symboles, $S_k$, does there exist a connected, undirected simple graph $G$ (no self loops, no multiple edges) of $deg(G) < (k-1)$ such that $S_k \subseteq Aut(G)$? That is, can you 'embed' a symmetric group, $S_k$ such that the degree of the graph is less than $k$?

Another way to say this is:

Can you find a graph of degree $d$ (or smaller) that has a group of $k > (d+1)$ vertices that you can permute?

I expect this problem to either be not possible or unknown so any ideas on why it couldn't be true or references would be welcome. I've done a little Googling but haven't found anything relevant.

If it turns out to be true, are there known bounds on the size of the graph relative to the degree and $k$?

Answer 1

Yes, the Peterson graph has 10 vertices and is 3-regular, and has $S_{5}$ as it's automorphism group.

More generally, the Johnson graph $J(n,k)$ is defined to be the graph whose vertices are subsets of size $k$ from a set of size $n$; two vertices are adjacent if and only if the subsets meet in a set of size $k-1$. This graph has ${n \choose k}$ vertices, is regular of degree $n-k$, and has $S_{n} \subseteq Aut(J(n,k))$. (I am reusing $k$ with a different meaning, which is bad form, but this is the standard notation for this family of graphs). Note that the Peterson graph is the complement of $J(5,2)$.