The $A_{\alpha}$ spectral radius of $k$-connected graphs with given diameter

For $d=2$ and $k\geq 2$, it is obvious that $G\in\mathcal{G}_{1}$. Next we consider $d\geq 3$ and $k\geq 2$.

By contradiction, we suppose $G\notin\mathcal{G}_{1}$, then there exists at least two $j_{1}$,…, $j_{s}\in\{1,2,\ldots,d-1\}$ such that $Z_{j_{1}},\ldots,Z_{j_{s}}\neq\emptyset$ $(s\geq 2)$ and $Z_{i}=\emptyset$ for each $i\in\{1,2,\ldots,d-1\}\setminus\{j_{1},\ldots,j_{s}\}$, which also implies that $|Z|\geq 2$.

For $d=3$ and $k\geq 2$, if $G\notin\mathcal{G}_{1}$, then $Z_{1}\neq\emptyset$ and $Z_{2}\neq\emptyset$. Let $G^{\prime}$ be a graph obtained from $G$ by deleting all edges between $Z_{1}$ and $V_{0}$ and adding all edges between $Z_{1}$ and $V_{d}$. Without loss of generality, we assume $x_{d}\geq x_{0}$. Since $|V_{0}|=|V_{d}|=1$, by using Lemma 2.7, we have $\lambda_{\alpha}(G^{\prime})>\lambda_{\alpha}(G)$. Note that $G^{\prime}\in\mathcal{G}_{1}\subseteq\mathcal{G}_{n,k}^{d}$, which contradicts the assumption that $G$ is the maximal graph in $\mathcal{G}_{n,k}^{k}$. Thus $G\in\mathcal{G}_{1}$.

Next we consider $d\geq 4$ and $k\geq 2$. Let $x_{a}\geq x_{b}\geq x_{c}$ be three largest values in the set $\{x_{i}|i=0,1,\ldots,d\}$ of the graph $G$, where $a$, $b$ and $c$ are pairwise distinct. Next we consider the following two cases:

• Case 1.

  $0$ or $d\notin\{a,b,c\}$.

  For any a vertex $v\in Z$, let $V_{a_{v}}(H),V_{b_{v}}(H),V_{c_{v}}(H)\in V(H)$ be three elements of the vertex partition set of $V(H)$, whose vertices are adjacent to $v$. It is possible that $\{a_{v},b_{v},c_{v}\}\cap\{a,b,c\}\neq\emptyset$. Because $\min\{x_{a},x_{b},x_{c}\}\geq\max\{x_{a_{v}},x_{b_{v}},x_{c_{v}}\}$, without loss of generality, we assume $x_{a}\geq x_{a_{v}}$, $x_{b}\geq x_{b_{v}}$ and $x_{c}\geq x_{c_{v}}$.

  • Step 1.

    Let $G_{1,1}$ be a graph obtained from $G$ by deleting all edges between $v$ and $V_{a_{v}}(H)$, $V_{b_{v}}(H)$, $V_{c_{v}}(H)$, respectively, and adding all edges between $v$ and $V_{a}(H)$, $V_{b}(H)$, $V_{c}(H)$, respectively.

    For $v\notin Z_{1}$ or $Z_{d-1}$, the graph $G$ and the graph $G_{1,1}$ ($v\notin Z_{1}$ or $Z_{d-1}$) is shown in Figure 3 ($a$), ($b$), respectively. In Figure 3 ($c$), we denote the edge-shifting operation from the graph $G$ to the graph $G_{1,1}$ ($v\notin Z_{1}$ or $Z_{d-1}$) as $G\rightarrow G_{1,1}$ ($v\notin Z_{1}$ or $Z_{d-1}$), where the thick dashed lines are the deleted edges in the graph $G$ and the thick solid lines are the added edges in the graph $G_{1,1}$. In Figures 3$-$9, take Figure 3 ($c$) as an example, we just show the edge-shifting operations between the corresponding two graphs.

    If $v\notin Z_{1}$ or $Z_{d-1}$, by using Equations (2) and (3), then

    		$\displaystyle\lambda_{\alpha}(G_{1,1})-\lambda_{\alpha}(G)$
    	$\displaystyle\geq$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,1})-A_{\alpha}(G)]X(G)$
    	$\displaystyle=$	$\displaystyle 2k(1-\alpha)x_{v}(x_{a}+x_{b}+x_{c}-x_{a_{v}}-x_{b_{v}}-x_{c_{v}})+$
    		$\displaystyle\alpha k(x_{a}^{2}+x_{b}^{2}+x_{c}^{2}-x_{a_{v}}^{2}-x_{b_{v}}^{2}-x_{c_{v}}^{2})\geq 0.$

    If $v\in Z_{1}$ or $Z_{d-1}$, by symmetry, we can suppose $v\in Z_{1}$. By using Equations (2) and (3), then we have

    		$\displaystyle\lambda_{\alpha}(G_{1,1})-\lambda_{\alpha}(G)$
    	$\displaystyle\geq$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,1})-A_{\alpha}(G)]X(G)$
    	$\displaystyle=$	$\displaystyle 2k(1-\alpha)x_{v}(x_{a}+x_{b}+x_{c}-x_{0}-x_{1}-x_{2})+\alpha k(x_{a}^{2}+x_{b}^{2}+x_{c}^{2}-x_{0}^{2}-x_{1}^{2}-x_{2}^{2})+$
    		$\displaystyle 2(k-1)\big{(}(1-\alpha)x_{v}x_{0}+\frac{\alpha}{2}x_{0}^{2}+\frac{\alpha}{2}x_{v}^{2}\big{)}\geq 0.$

    Therefore, $\lambda_{\alpha}(G_{1,1})>\lambda_{\alpha}(G)$.

    

    

    

  • Step 2.

    Let $w$ be a vertex of $G$ and $w\in Z\setminus\{v\}$.
    If $w\notin Z_{1}$ or $Z_{d-1}$, let $V_{a_{w}}(H),V_{b_{w}}(H),V_{c_{w}}(H)\in V(H)$ be three elements of the vertex partition set of $V(H)$, whose vertices are adjacent to $w$. According to our assumption, $\min\{x_{a},x_{b},x_{c}\}\geq\max\{x_{a_{w}},x_{b_{w}},x_{c_{w}}\}$, thus without loss of generality, we assume $x_{a}\geq x_{a_{w}}$, $x_{b}\geq x_{b_{w}}$, $x_{c}\geq x_{c_{w}}$. Next we do the same operation as Step 1. and obtain a graph $G_{1,2}$ from $G_{1,1}$ by deleting all edges between $w$ and $V_{a_{w}}(H)$, $V_{b_{w}}(H)$, $V_{c_{w}}(H)$, respectively, and adding all edges between $w$ and $V_{a}(H)$, $V_{b}(H)$, $V_{c}(H)$, respectively. Then

    		$\displaystyle\lambda_{\alpha}(G_{1,2})-\lambda_{\alpha}(G)$
    	$\displaystyle\geq$	$\displaystyle X(G_{1,2})^{T}A_{\alpha}(G_{1,2})X(G_{1,2})-X(G)^{T}A_{\alpha}(G)X(G)$
    	$\displaystyle\geq$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,2})-A_{\alpha}(G)]X(G)$
    	$\displaystyle=$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,2})-A_{\alpha}(G_{1,1})]X(G)+X(G)^{T}[A_{\alpha}(G_{1,1})-A_{\alpha}(G)]X(G)$
    	$\displaystyle\geq$	$\displaystyle 2k(1-\alpha)x_{w}(x_{a}+x_{b}+x_{c}-x_{a_{w}}-x_{b_{w}}-x_{c_{w}})+$
    		$\displaystyle\alpha k(x_{a}^{2}+x_{b}^{2}+x_{c}^{2}-x_{a_{w}}^{2}-x_{b_{w}}^{2}-x_{c_{w}}^{2})\geq 0.$

    If $w\in Z_{1}$ or $Z_{d-1}$, by symmetry, we suppose $w\in Z_{1}$. By using Equations (2) and (3), then we have

    		$\displaystyle\lambda_{\alpha}(G_{1,2})-\lambda_{\alpha}(G)$
    	$\displaystyle=$	$\displaystyle\lambda_{\alpha}(G_{1,2})-\lambda_{\alpha}(G_{1,1})+\lambda_{\alpha}(G_{1,1})-\lambda_{\alpha}(G)$
    	$\displaystyle\geq$	$\displaystyle X(G_{1,2})^{T}A_{\alpha}(G_{1,2})X(G_{1,2})-X(G)^{T}A_{\alpha}(G)X(G)$
    	$\displaystyle\geq$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,2})-A_{\alpha}(G)]X(G)$
    	$\displaystyle=$	$\displaystyle X(G)^{T}[A_{\alpha}(G_{1,2})-A_{\alpha}(G_{1,1})]X(G)+X(G)^{T}[A_{\alpha}(G_{1,1})-A_{\alpha}(G)]X(G)$
    	$\displaystyle\geq$	$\displaystyle 2k(1-\alpha)x_{w}(x_{a}+x_{b}+x_{c}-x_{a_{w}}-x_{b_{w}}-x_{c_{w}})+$
    		$\displaystyle\alpha k(x_{a}^{2}+x_{b}^{2}+x_{c}^{2}-x_{a_{w}}^{2}-x_{b_{w}}^{2}-x_{c_{w}}^{2})+$
    		$\displaystyle 2(k-1)\big{(}(1-\alpha)x_{w}x_{0}+\frac{\alpha}{2}x_{0}^{2}+\frac{\alpha}{2}x_{w}^{2}\big{)}\geq 0.$

    Repeat this step until all of the vertices in $Z$ have been chosen. Thus in the final graph, denoted by $G_{2}$, all vertices in $Z$ are adjacent to $V_{a}(H)$, $V_{b}(H)$ and $V_{c}(H)$, and $\lambda_{\alpha}(G_{2})>\lambda_{\alpha}(G)$.

    In order to ensure that the maximal graph $G$ after the edge-shifting operation is still a diameter critical graph, and prove that our conclusions hold, we do the Step 3.

  • Step 3.

    Let $G_{2,1}$ be the graph obtained from $G_{2}$ by adding some edges so that $G_{2,1}[Z]$ is a clique. Then $\lambda_{\alpha}(G_{2,1})>\lambda_{\alpha}(G_{2})>\lambda_{\alpha}(G)$.
    If $G[V_{a}(H)\cup V_{b}(H)\cup V_{c}(H)]=K_{k}\vee K_{k}\vee K_{k}$, then our results hold. Next we consider the following two cases.

    • Case 1.1.

      

      $G[V_{a}(H)\cup V_{b}(H)\cup V_{c}(H)]=(K_{k}\vee K_{k})\cup K_{k}$.

      Let $G_{2,2}$ be the graph obtained from $G_{2,1}$ by deleting all edges between $V_{b}(H)$ and $V_{b+1}(H)$, all edges between $V_{c}(H)$ and $V_{c+1}(H)$, and adding all edges between $V_{b}(H)$ and $V_{c}(H)$, all edges between $V_{b+1}(H)$ and $V_{c+1}(H)$, as shown in Figure 4.

      If $c+1\neq d$, then

      $\displaystyle\lambda_{\alpha}(G_{2,2})-\lambda_{\alpha}(G_{2,1})\geq 2(1-\alpha)k^{2}(x_{b}-x_{c+1})(x_{c}-x_{b+1})\geq 0.$

      If $c+1=d$, then

      	$\displaystyle\lambda_{\alpha}(G_{2,2})-\lambda_{\alpha}(G_{2,1})\geq$	$\displaystyle 2(1-\alpha)k^{2}(x_{b}-x_{c+1})(x_{c}-x_{b+1})+$
      		$\displaystyle 2(1-\alpha)k(k-1)(x_{c+1}x_{c}-x_{b+1}x_{c+1})+$
      		$\displaystyle\alpha k(k-1)(x_{c}^{2}-x_{b+1}^{2})\geq 0.$

      Then $\lambda_{\alpha}(G_{2,2})>\lambda_{\alpha}(G_{2,1})>\lambda_{\alpha}(G_{2})>\lambda_{\alpha}(G)$, and $G_{2,2}\in\mathcal{G}_{1}\subset\mathcal{G}_{n,k}^{d}$. This contradicts that $G\notin\mathcal{G}_{1}$ is the maximal graph in $\mathcal{G}_{n,k}^{k}$. Thus the maximal graph $G\in\mathcal{G}_{1}\subset\mathcal{G}_{n,k}^{d}$.

    • Case 1.2.

      

      $G[V_{a}(H)\cup V_{b}(H)\cup V_{c}(H)]=K_{k}\cup K_{k}\cup K_{k}$.
      Let $G_{2,3}$ be the graph obtained from $G_{2,1}$ by deleting all edges between $V_{a}(H)$ and $V_{a+1}(H)$, all edges between $V_{b}(H)$ and $V_{b+1}(H)$, all edges between $V_{c}(H)$ and $V_{c+1}(H)$, all edges between $V_{b}(H)$ and $V_{b-1}(H)$, and adding all edges between $V_{a}(H)$ and $V_{b}(H)$, all edges between $V_{b}(H)$ and $V_{c}(H)$, all edges between $V_{a+1}(H)$ and $V_{b+1}(H)$, all edges between $V_{b-1}(H)$ and $V_{c+1}(H)$, as shown in Figure 5.

      If $c+1\neq d$, then

      		$\displaystyle\lambda_{\alpha}(G_{2,3})-\lambda_{\alpha}(G_{2,1})$
      	$\displaystyle\geq$	$\displaystyle 2(1-\alpha)k^{2}[(x_{a}-x_{b+1})(x_{b}-x_{a+1})+(x_{b}-x_{c+1})(x_{c}-x_{b-1})]\geq 0.$

      If $c+1=d$, then

      		$\displaystyle\lambda_{\alpha}(G_{2,3})-\lambda_{\alpha}(G_{2,1})$
      	$\displaystyle\geq$	$\displaystyle 2(1-\alpha)k^{2}[(x_{a}-x_{b+1})(x_{b}-x_{a+1})+(x_{b}-x_{c+1})(x_{c}-x_{b-1})]+$
      		$\displaystyle 2(1-\alpha)k(k-1)(x_{c}x_{c+1}-x_{b-1}x_{c+1})+\alpha k(k-1)(x_{c}^{2}-x_{b-1}^{2})\geq 0.$

      Then $\lambda_{\alpha}(G_{2,3})>\lambda_{\alpha}(G_{2,1})>\lambda_{\alpha}(G)$ and $G_{2,3}\in\mathcal{G}_{1}\subset\mathcal{G}_{n,k}^{d}$. This contradicts that $G\notin\mathcal{G}_{1}$ is the maximal graph in $\mathcal{G}_{n,k}^{d}$. Thus the maximal graph $G\in\mathcal{G}_{1}\subset\mathcal{G}_{n,k}^{d}$.

• Case 2.

  $0$ or $d\in\{a,b,c\}$.
  Since $x_{0}=\frac{(1-\alpha)|V_{1}|}{\lambda_{\alpha}-\alpha|V_{1}|}x_{1}$, by using Proposition 36. in [19] and Lemma 2.3, then $\lambda_{\alpha}>(|V_{1}|+1)-1=|V_{1}|$, that is $x_{0}<x_{1}$. Because of symmetry, we have $x_{d}<x_{d-1}$. Thus, $\{a,b,c\}=\{0,1,r\}$ or $\{r,d-1,d\}$, where $1\leq r\leq d-1$. Without loss of generality, we assume $\{a,b,c\}=\{0,1,r\}$, where $2\leq r\leq d-1$. Next we consider two cases: first, $Z_{1}=Z_{d-1}=\emptyset$, second, $Z_{1}\neq Z_{d-1}\neq\emptyset$. The case of $Z_{1}\neq Z_{d-1}\neq\emptyset$ can be converted to the case that $Z_{1}\neq\emptyset$ and $Z_{d}\neq\emptyset$ by using some edge-shifting operations.

  • 

    

    

    

    

    

  • Case 2.1.

    $Z_{1}=Z_{d-1}=\emptyset$.
    Let $x_{a^{\prime}}\geq x_{b^{\prime}}\geq x_{c^{\prime}}$ be the three largest components of $X(G)\setminus\{x_{0},x_{d}\}=(x_{1},x_{2},\ldots,x_{d-1})^{T}$ corresponding to all vertices of $V_{a^{\prime}}$, $V_{b^{\prime}}$, $V_{c^{\prime}}$ ($a^{\prime}$, $b^{\prime}$ and $c^{\prime}$ are pairwise distinct), respectively. We follow all steps as Case 1., then we can obtain the graphs like $G_{1,1}$, $G_{1,2}$, $G_{2,1}$, $G_{2}$, $G_{2,2}$ or $G_{2,3}$, such that $\lambda_{\alpha}(G_{2,3})\big{(}\lambda_{\alpha}(G_{2,2})\big{)}>\lambda_{\alpha}(G_{2,1})>\lambda_{\alpha}(G_{2})\big{(}\lambda_{\alpha}(G_{1,2}),\lambda_{\alpha}(G_{1,1})\big{)}>\lambda_{\alpha}(G)$, where $G_{2,3}$ and $G_{2,2}$ are in $\mathcal{G}_{1}\subseteq\mathcal{G}_{n,k}^{d}$. Then we obtain a same contradiction like Case 1. that $G$ is a maximal graph in $\mathcal{G}_{n,k}^{d}$ and $G\notin\mathcal{G}_{1}$.

  • Case 2.2.

    $Z_{1}\neq Z_{d-1}\neq\emptyset$ and $r\neq d-1$.
    Let $G_{3,1}$ be a graph obtained from $G$ by deleting all edges between $Z_{d-1}$ and $V_{d}(H)$, $V_{d-1}(H)$, respectively, and adding all edges between $Z_{d-1}$ and $V_{0}(H)$, $V_{1}(H)$, respectively, as shown in Figure 6. Then there is no edge between $Z$ and $V_{d-1}(H)\cup V_{d}(H)$. By using Lemma 2.8, then $\lambda_{\alpha}(G_{3,1})>\lambda_{\alpha}(G)$. The following discussion also applies to the case that one of $Z_{1}$, $Z_{d-1}$ is not an empty set.

    First, we choose one vertex $w$ from $V_{d-1}(H)$. Let $G_{3,2}$ be a graph obtained from $G$ by deleting all edges between $w$ and $(V_{d-1}(H)\setminus{w})\cup V_{d}(H)$, all edges between $V_{d-2}(H)$ and $V_{d-1}(H)\setminus{w}$, and adding all edges between $V_{d-1}(H)\setminus{w}$ and $V_{1}(H)\cup V_{0}(H)$, and the edge $V_{0}V_{d}$, see Figure 7. By using Lemma 2.8, we have $\lambda_{\alpha}(G_{3,2})>\lambda_{\alpha}(G)$.

    Second, let $G_{3,3}$ be a graph obtained from $G_{3,2}$ by adding all edges between $V_{d-1}\setminus{w}$ and $Z_{1}$, as shown in Figure 8. By using Lemma 2.3, we have $\lambda_{\alpha}(G_{3,3})>\lambda_{\alpha}(G)$.

    Third, if $Z_{d-2}=\emptyset$, then we may follow the proof of Case 1., otherwise, if $Z_{d-2}\neq\emptyset$, let $G_{3,4}$ be a graph obtained from $G_{3,3}$ by deleting all edges between $w$ and $Z_{d-2}$, and adding all edges between $V_{0}$ and $Z_{d-2}$, as shown in Figure 9. By using Lemma 2.8, we have $\lambda_{\alpha}(G_{3,4})>\lambda_{\alpha}(G)$. Next, we may follow the proof of Case 1. and get a contraction. Thus the maximal graph $G\in\mathcal{G}_{1}\subset\mathcal{G}_{n,k}^{d}$.

  • Case 2.3.

    $Z_{1}\neq Z_{d-1}\neq\emptyset$ and $r=d-1$ ($\{a,b,c\}=\{0,1,r\}$).
    First, we keep all edges between $Z_{1}$ and $V_{0}\cup V_{1}(H)$, keep all edges between $Z_{d-1}$ and $V_{d-1}(H)$. Next we delete all edges between $Z_{d-1}$ and $V_{d}$ and add all edges between $Z_{d-1}$ and $V_{0}$.

    Second, let $x_{j}$ be the largest component of $X(G)\setminus\{x_{0},x_{1},x_{d-1},x_{d}\}$. Then we repeat the similar operations of Step 1.–Step 3. in Case 1. and obtain a graph $G_{3,5}$ with $\lambda_{\alpha}(G_{3,5})>\lambda_{\alpha}(G)$, as shown in Figure 10. Let $G_{3,6}$ be a graph obtained from $G_{3,5}$ by deleting all edges between $Z_{1}$ and $V_{j}(H)$, all edges between $Z_{d-1}$ and $V_{j}(H)$, and adding all edges between $Z_{1}$ and $V_{d-1}(H)$, all edges between $Z_{d-1}$ and $V_{1}(H)$, as shown in Figure 11. Then by using Lemma 2.3, we have $\lambda_{\alpha}(G_{3,5})>\lambda_{\alpha}(G)$. Note that the graph $G_{3,6}$ satisfys $G_{3,6}\in\mathcal{G}_{n.k}^{d}$, and in the graph $G_{3,6}$, one of $Z_{1}$ and $Z_{d-1}\neq\emptyset$ and $r\neq d-1$. It belongs to Case 2.2.