For a group $G$ and an inverse closed subset $S$ of $G\setminus \{1\}$, the Cayley graph $Cay(G,S)$, is the graph whose vertices are the elements of $G$ and two vertices $x$ and $y$ are adjacent if and only if $xy^{-1}\in S$. Let $a,a^{-1}$ are two elements of $G$ that are not in $S$. Also suppose $d$ be the diameter of $Cay(G,S)$ and $d'$ is diameter of $Cay(G,S\cup{\{a,a^{-1}\}} )$. Given $G$ and $d$, can we determine $d'$?


I will be so thankful for any helpful comments and answers.



diameter of Cayley graphs
Suppose $G$ is a finite group and we choose $S'=G\setminus\{1,a,a^{-1}\}$. Then if we let $S=S'\cup \{a,a^{-1}\}$, the diameter of the cayley graph $Cay(G,S)$ is one, but the diameter of the Cayley graph $Cay(G,S')$ is not one (it seems it is two). In contrast, we have a lot of large Cayley graphs with diameter two, and by adding an element and its inverse to their generating sets, the diameter does not change. If the group $G$ is abelian and $|S|=m$, we can prove the below bounds in general:


$$\frac{1}{e}|G|^{\frac{1}{m+2}}\leq diam(Cay(G,S\cup \{a,a^{-1}\}))\leq diam(Cay(G,S)).$$


Determining the diameter of a Cayley graphs is related to the diameter of its group and generating set, which is shown to be $NP-$hard. 


