A strongly connected digraph \(D\) is primitive provided the greatest common divisor of the lengths of its directed cycles equals 1. The scrambling index of a primitive digraph \(D\) is the smallest positive integer \(k\) such that for every pair of vertices \(u\) and \(v\), there is a vertex \(w\) such that we can get to \(w\) from \(u\) and \(v\) in \(D\) by directed walks of length \(k\). In this paper, we characterize those primitive doubly symmetric digraphs with the largest scrambling index.
Let \(D=(V,E)\) denote a digraph with vertex set \(V=V(D)\) and arc set \(E=E(D)\). Loops are permitted, but not multiple arcs. An \(u\to v\) walk in \(D\) is a sequence of vertices \(u,u_1,\cdots,u_p=v\) and a sequence of arcs \((u,u_1)\), \((u_1,u_2),\cdots,(u_{p-1},v)\), where the vertices and the arcs are not necessarily distinct. A closed walk is an \(u\to v\) walk, where \(u=v\). A path is a walk with distinct vertices. A cycle is a closed \(u\to v\) walk with distinct vertices except for \(u=v\). The length of a walk \(W\) is the number of arcs in \(W\), and denoted by \(|W|\). The notation \(u\xrightarrow{k}v\) is used to indicate that there is an \(u\to v\) walk of length \(k\). The distance from vertex \(u\) to vertex \(v\) in \(D\), is the length of a shortest walk from \(u\) to \(v\), and denoted by \(d(u,v)\).
A digraph \(D\) is strongly connected if there is an \(u\to v\) path for each pair \(u,v\) of vertices of \(D\). A strongly connected digraph \(D\) is primitive provided the greatest common divisor of the lengths of its directed cycles equals 1. It is well known (see e.g. [4]) that a digraph \(D\) is primitive if and only if there exists some positive integer \(k\) such that \(u\xrightarrow{k}v\) for all ordered pairs of vertices \(u\) and \(v\) (not necessarily distinct) of \(D\). The smallest such \(k\) is called the primitive exponent of \(D\), denoted by \(\gamma(D)\).
In [3], by using Seneta’s [13] definition of coefficients of ergodicity, Akelbek and Kirkland provided an attainable upper bound on the second largest moduli of eigenvalues of a primitive matrix that makes use of the so-called scrambling index. The scrambling index of a primitive digraph \(D\), denoted by \(k(D)\), is the smallest positive integer \(k\) such that for every pair of vertices \(u\) and \(v\), there exists a vertex \(w\) such that \(u\xrightarrow{k}w\) and \(v\xrightarrow{k}w\) in \(D\).
Akelbek and Kirkland’s [3] definition of scrambling index is the same as Cho and Kim’s [8] definition of the competition index in the case of primitive digraphs. The scrambling index (competition index) have an interpretation in stochastic matrices and food webs. For the research on scrambling index and competition index, please refer to [3, 2, 1, 7, 11, 15, 16, 8, 9, 10] respectively.
A symmetric digraph is a digraph if for any pair of vertices \(u\) and \(v\), \((u,v)\) is an arc if and only if \((v,u)\) is an arc. An undirected graph (possibly with loops) can be regarded as a symmetric digraph. It is well known (see e.g. [14]) that an undirected graph \(G\) is primitive if and only if \(G\) is connected and has at least one odd cycle.
A symmetric digraph \(G\) with \(V(G)=\{1,2,\cdots,n\}\) is called a doubly symmetric digraph if there is a vertex label such that for any pair of vertices \(i\) and \(j\), \([i,j]\) is an edge if and only if \([n+1-i,n+1-j]\) is an edge. The vertex \(n+1-i\) is called the doubly symmetric vertex of \(i\), denoted by \(i^d\). Note that if \(n\equiv 1(\mathrm{mod}\ 2)\) and \(i=\frac{n+1}{2}\), then \(i=i^d\); otherwise, we always have \(i\ne i^d\) for \(i\in V(G)\). If \(W=i_1i_2\cdots i_m\) is a walk from a vertex \(i_1\) to a vertex \(i_m\) in \(G\), then \(W^d=i_1^di_2^d\cdots i_m^d\) is a walk from \(i_1^d\) to \(i_m^d\) in \(G\).
Let \(DS(n)\) denote the set of all primitive doubly symmetric digraphs of order \(n\ge 3\). Liu and Huang [11] obtained the upper bound on the scrambling index of \(G\in DS(n)\), that is \[\max\{k(G)|\ G\in DS(n)\}=\left\lceil\frac{n-1}{2}\right\rceil . \label{eq1.1} \tag{1}\]
The extremal digraph problem is a main problem in the study of primitive exponents. The problem of complete characterization of the extremal digraphs of certain primitive digraph classes is usually very difficult. In this paper, we give a complete characterization of those primitive doubly symmetric digraphs with the maximum scrambling index.
For a primitive digraph \(D\), the exponent from vertex \(u\) to vertex \(v\), denoted by \(\gamma_D(u,v)\), is the least integer \(p\) such that there exists an \(u\to v\) walk of length \(t\) for all \(t\ge p\). Clearly, \[\gamma(D)=\max\{\gamma_D(u,v)|\ u,v\in V(D)\}. \label{eq2.1} \tag{2}\]
Lemma 2.1. [12] Let \(G\) be a primitive symmetric digraph, and let \(u,v\) be any pair of vertices of \(G\). If \(u\xrightarrow{k_1}v\) and \(u\xrightarrow{k_2}v\), where \(k_1-k_2\equiv 1(\mathrm{mod}\ 2)\), then \[\gamma_G(u,v)\le \max\{k_1,k_2\}-1. \label{eq2.2} \tag{3}\]
Lemma 2.2. [5] Let \(n\) be an integer with \(n\ge 3\). Then \[\max\{\gamma(G)|\ G\in DS(n)\}=n-1. \label{eq2.3} \tag{4}\]
Let \(G=(V,E)\) be a connected graph. For a vertex \(u\in V\) and a nonempty set \(X\subseteq V\), let \(d(u,X)=\min\{d(u,x)|\ x\in X\}\). For \(u\in X\), we define \(d(u,X)=0\). For a cycle \(C\), if \(u,v\) are two vertices (not necessarily distinct) on \(C\), then \(Q_C(u,v)\) denotes the shortest path from \(u\) to \(v\) along \(C\) (note that \(Q_C(u,v)\) has no edge when \(u=v\)), and \(C\backslash Q_C(u,v)\) denotes the path or cycle from \(u\) to \(v\) along \(C\) obtained by deleting the edges of \(Q_C(u,v)\). For a path \(P\) and \(u,v\in V(P)\), the subpath between \(u\) and \(v\) of \(P\) is denoted by \(P_{uv}\). The concatenation of a walk \(W_1\) from \(u\) to \(v\), and a walk \(W_2\) from \(v\) to \(w\) is denoted by \(W_1+W_2\).
Lemma 2.3. Let \(G\) be a connected graph containing a primitive subgraph \(G_1\). Then \(G\) is primitive and \[\gamma(G)\le \gamma(G_1)+2\max\{d(u,V(G_1))|\ u\in V(G)\}. \label{eq2.4} \tag{5}\]
Proof. Let \(k=\max\{d(u,V(G_1))|\ u\in V(G)\}\), and let \(x\) and \(y\) be any two vertices (not necessarily distinct) in \(G\). Since \(G\) is connected, there is a walk from \(x\) to each vertex in \(G_1\) and a walk from each vertex in \(G_1\) to \(y\), and there are vertices \(v_1\) and \(v_2\) in \(G_1\) such that the distances \(d(x,v_1)\) and \(d(v_2,y)\) are at most \(k\). Since \(G_1\) is primitive, there is a walk in \(G_1\) from \(v_1\) to \(v_2\) of length \(\gamma(G_1)+2k-[d(x,v_1)+d(v_2,y)]\). That is, in \(G\) there is a walk from \(x\) to \(y\) of length \(\gamma(G_1)+2k\), and hence \(\gamma(G)\le \gamma(G_1)+2k\). ◻
Lemma 2.4. Let \(G=C_1\cup C_2\), where \(C_1\) and \(C_2\) are two odd cycles of \(G\). If \(\min\{|C_1|,|C_2|\}\\ \ge 3\) and \(|V(C_1)\cap V(C_2)|\ge 1\), then \(\gamma(G)\le \max\{|C_1|,|C_2|\}-1\).
Proof. Let \(x\) and \(y\) be any two vertices (not necessarily distinct) in \(G\). We only need to consider the following two cases:
Case 1. \(x,y\in V(C_i)\), \(i=1,2\). Then \(Q_{C_i}(x,y)\) and \(C_i\backslash Q_{C_i}(x,y)\) are two walks in \(G\) from \(x\) to \(y\) on \(C_i\). Since \(|C_i|\equiv 1(\mathrm{mod}\ 2)\), \(|C_i\backslash Q_{C_i}(x,y)|-|Q_{C_i}(x,y)|\equiv 1(\mathrm{mod}\ 2)\). It follows from (2.2) that \[\gamma_G(x,y)\le \max\{|C_i\backslash Q_{C_i}(x,y)|, |Q_{C_i}(x,y)|\}-1\le \max\{|C_1|,|C_2|\}-1.\]
Case 2. \(x\in V(C_1)\), \(y\in V(C_2)\). Since \(|V(C_1)\cap V(C_2)|\ge 1\), there is a vertex \(z\in V(C_1)\cap V(C_2)\). Set \[\begin{aligned} W_1=&Q_{C_1}(x,z)+Q_{C_2}(z,y),\\ W_2=&\begin{cases} Q_{C_1}(x,z)+C_2\backslash Q_{C_2}(z,y),& \text{if } |C_1\backslash Q_{C_1}(x,z)|\ge |C_2\backslash Q_{C_2}(z,y)|,\\ C_1\backslash Q_{C_1}(x,z)+Q_{C_2}(z,y),& \text{if } |C_1\backslash Q_{C_1}(x,z)|\le |C_2\backslash Q_{C_2}(z,y)|. \end{cases} \end{aligned}\]
Then \(W_1\) and \(W_2\) are walks of different parity between \(x\) and \(y\) , and \[|W_1|\le \frac{|C_1|-1}{2}+\frac{|C_2|-1}{2}\le \max\{|C_1|,|C_2|\}-1,\] \[|W_2|\le \begin{cases} |C_1|, & \text{if } |C_1\backslash Q_{C_1}(x,z)|\ge |C_2\backslash Q_{C_2}(z,y)|,\\ |C_2|, & \text{if } |C_1\backslash Q_{C_1}(x,z)|\le |C_2\backslash Q_{C_2}(z,y)|. \end{cases}\]
It follows from (3) that \[\gamma_G(x,y)\le \max\{|W_1|,|W_2|\}-1\le \max\{|C_1|,|C_2|\}-1.\]
Thus in any case we have that \(\gamma_G(x,y)\le \max\{|C_1|,|C_2|\}-1\). Since \(x\) and \(y\) are arbitrary vertices of \(G\), the result now follows by (2). ◻
Lemma 2.5. Let \(G=C_1\cup P\cup C_2\), where \(C_1\) and \(C_2\) are two non-intersecting cycles, and \(P\) is a path such at \(V(P)\cap V(C_i)=\{z_i\}\) \((i=1,2)\), where \(z_1\) and \(z_2\) are the endvertices of \(P\). If \(\min\{|C_1|,|C_2|\}\ge 3\) and \(|C_i|\equiv 1(\mathrm{mod}\ 2)\) \((i=1,2)\), then \(\gamma(G)\le |C_1|+|P|+|C_2|-4\).
Proof. Let Let \(x\) and \(y\) be any two vertices (not necessarily distinct) in \(G\). We consider the following cases:
Case 1. \(x,y\in V(C_i)\), \(i=1,2\). Then \(Q_{C_i}(x,y)\) and \(C_i\backslash Q_{C_i}(x,y)\) are two walks of different parity between \(x\) and \(y\) in \(G\). By Lemma 2.1 we have \[\gamma_G(x,y)\le |C_i|-1\le |C_1|+|P|+|C_2|-4.\]
Case 2. \(x\in V(P)\), \(y\in V(C_i)\), \(i=1,2\). Let \(W_1=P_{xz_i}+Q_{C_i}(z_i,y)\) and \(W_2=P_{xz_i}+C_i\backslash Q_{C_i}(z_i,y)\). Then \(W_1\) and \(W_2\) are walks of different parity between \(x\) and \(y\). It follows from Lemma 2.1 that \[\gamma_G(x,y)\le |P_{xz_i}|+|C_i|-1\le |C_1|+|P|+|C_2|-4.\]
Case 3. \(x,y\in V(P)\). Without loss of generality, we may assume \(P=P_{z_1x}+P_{xy}+P_{yz_2}\). Set \[\begin{aligned} W_1=&\begin{cases} P_{xz_1}+P_{z_1x}+P_{xy}, & \text{if } |P_{xz_1}|\le |P_{yz_2}|,\\ P_{xy}+P_{yz_2}+P_{z_2y}, & \text{if } |P_{xz_1}|\ge |P_{yz_2}|. \end{cases}\\ W_2=&\begin{cases} P_{xz_1}+C_1+P_{z_1x}+P_{xy}, & \text{if } |P_{xz_1}|\le |P_{yz_2}|,\\ P_{xy}+P_{yz_2}+C_2+P_{z_2y}, & \text{if } |P_{xz_1}|\ge |P_{yz_2}|. \end{cases} \end{aligned}\]
Then \(W_1\) and \(W_2\) are walks of different parity between \(x\) and \(y\) , and \[|W_1|<|W_2|\le \begin{cases} |C_1|+|P|, & \text{if } |P_{xz_1}|\le |P_{yz_2}|,\\ |C_2|+|P|, & \text{if } |P_{xz_1}|\ge |P_{yz_2}|. \end{cases}\]
Hence by Lemma 2.1 we have that \[\gamma_G(x,y)\le \max\{|C_1|,|C_2|\}+|P|-1\le |C_1|+|P|+|C_2|-4.\]
Case 4. \(x\in V(C_1)\backslash\{z_1\}\), \(y\in V(C_2)\backslash\{z_2\}\). Let \(W_1=Q_{C_1}(x,z_1)+P+Q_{C_2}(z_2,y)\) and \(W_2=Q_{C_1}(x,z_1)+P+C_2\backslash Q_{C_2}(z_2,y)\). Then \(|W_1|-|W_2|\equiv 1(\mathrm{mod}\ 2)\), so by Lemma 2.1 we have \[\gamma_G(x,y)\le \frac{|C_1|-1}{2}+|P|+|C_2|-1-1\le |C_1|+|P|+|C_2|-4.\]
Thus in any case we have that \(\gamma_G(x,y)\le |C_1|+|P|+|C_2|-4\). Since \(x\) and \(y\) are arbitrary vertices of \(G\), the result now follows by (2). ◻
Lemma 2.6. Let \(G\in DS(n)\) with \(V(G)=\{1,2,\ldots,n\}\), and let \(X\) be any nonempty proper subset of \(V(G)\), satisfying \(x\in X\) if and only if \(x^d\in X\). Let \(u\) be any vertex in \(V(G)\backslash X\), and let \(v\in X\) such that \(d(u,v)=d(u,X)\). If \(P\) is a shortest path between \(u\) and \(v\), then \(V(P)\cap V(P^d)=\varphi\) or \(V(P)\cap V(P^d)=\{\frac{n+1}{2}\}\).
Proof. If \(V(P)\cap V(P^d)=\varphi\), then the result follows.
Suppose now \(V(P)\cap V(P^d)\ne \varphi\). Let \(w\) be any vertex in \(V(P)\cap V(P^d)\). Then \(w^d\in V(P)\cap V(P^d)\). Without loss of generality, we may assume \(P=P_{uw}+P_{ww^d}+P_{w^dv}\). Then \((P_{w^dv})^d\) is a path of length \(|(P_{w^dv})^d|=|P_{w^dv}|\) between \(w\) and \(v^d\), and so \(P_{uw}+(P_{w^dv})^d\) is a walk between \(u\) and \(v^d\). Notice that \(d(u,X)=|P|=|P_{uw}|+|P_{ww^d}|+|P_{w^dv}|\) and \(v^d\in X\), so we have \[|P_{uw}|+|P_{ww^d}|+|P_{w^dv}|\le d(u,v^d)\le |P_{uw}+(P_{w^dv})^d|=|P_{uw}|+|P_{w^dv}|.\]
Hence we conclude \(|P_{ww^d}|=0\), that is \(w=w^d\). But \(w\) is an arbitrary vertex in \(V(P)\cap V(P^d)\), so we have \(V(P)\cap V(P^d)=\{\frac{n+1}{2}\}\), as desired. ◻
Lemma 2.7. Let \(n\) be an odd integer with \(n\ge 5\), and let \(G\in DS(n)\). If \(G\) contains an odd cycle \(C\) with \(|C|\ge 3\) and \(|V(C)\cap V(C^d)|=0\), then \(\gamma(G)\le n-3\).
Proof. Let \(u\in V(C)\) such that \(d(\frac{n+1}{2},u)=d(\frac{n+1}{2},V(C))\), and let \(P\) be a shortest path between \(\frac{n+1}{2}\) and \(u\). Then \(P^d\) is a shortest path between \(\frac{n+1}{2}\) and \(u^d\), and \(|P|=|P^d|=d(\frac{n+1}{2},V(C^d))\). By Lemma 2.6, \(P+P^d\) is a path joining the non-intersecting cycles \(C\) and \(C^d\). Let \(G_1=C\cup(P+P^d)\cup C^d\), it follows from Lemma 2.5 that \[\gamma(G_1)\le 2(|C|+|P|)-4.\]
Notice that the vertex \(\frac{n+1}{2}\in V(G_1)\) and \(V(G_1)=V(G_1^d)\), we have by Lemma 2.6 that \[\max\{d(v,V(G_1))|\ v\in V(G)\}\le \frac{n-|V(G_1)|}{2}.\]
Since \(|V(G_1)|=2(|C|+|P|)-1\), it follows from Lemma 2.3 that \[\gamma(G)\le 2(|C|+|P|)-4+n-|V(G_1)|=n-3.\]
The Lemma now follows. ◻
Lemma 2.8. Let \(n\) be an odd integer with \(n\ge 5\), and let \(G\in DS(n)\). If
\(\max\{|C|\ |\ C \text{ is an odd cycle of }
G\}=1\), then \(\gamma(G)\ne
n-2\).
Proof. Let \(v\in V(G)\) such that \(d(v,\frac{n+1}{2})=\max\{d(i,\frac{n+1}{2})|i\in V(G)\}\). Then by Lemma 2.6 we have \(d(v,\frac{n+1}{2})\le \frac{n-1}{2}\). We consider the following two cases:
Case 1. There is a loop at the vertex \(\frac{n+1}{2}\). Then for any vertices \(i,j\in V(G)\), and for any integer \(t\ge d(i,\frac{n+1}{2})+d(j,\frac{n+1}{2})\), there is an \(i\to j\) walk of length \(t\). So \(\gamma_G(i,j)\le d(i,\frac{n+1}{2})+d(j,\frac{n+1}{2})\le 2d(v,\frac{n+1}{2})\). Since \(i\) and \(j\) are arbitrary vertices of \(G\), it follows that \(\gamma(G)=\max\{\gamma_G(i,j)|i,j\in V(G)\}\le 2d(v,\frac{n+1}{2})\).
If \(d(v,\frac{n+1}{2})\le \frac{n-3}{2}\), then \(\gamma(G)\le 2d(v,\frac{n+1}{2})\le n-3\).
If \(d(v,\frac{n+1}{2})=\frac{n-1}{2}\), then \(G\) has a spanning subgraph \(G_0\) obtained from \(P+P^d\) and the loop at \(\frac{n+1}{2}\), where \(P\) is a shortest path between \(v\) and \(\frac{n+1}{2}\). For the sake of convenience, let \(P=12\cdots(\frac{n-1}{2})(\frac{n+1}{2})\). This implies that \(v=1\) and \(P^d=n(n-1)\cdots(\frac{n+3}{2})(\frac{n+1}{2})\).
If \(d(1,n)=n-1\), then \(\gamma_G(1,n)=d(1,n)=n-1\). Hence \(\gamma(G)=n-1\).
If \(d(1,n)<n-1\), then there must be an edge joining a vertex \(i\in V(P)\backslash\{\frac{n+1}{2}\}\) and a vertex \(j\in V(P^d)\backslash\{\frac{n+1}{2}\}\).
Assume that \(j=i^d\). Then \(G\) contains an odd cycle with length \(2(\frac{n+1}{2}-i)+1\ge 3\), a contradiction.
Assume that \(|j-i^d|\ge 2\). Notices that there is an \([i^d,j^d]\in E(G)\), then \(d(1,\frac{n+1}{2})=d(n,\frac{n+1}{2})\leqslant \frac{n-3}{2}\), a contradiction.
Thus \(|j-i^d|=1\). Without loss of generality, we may assume that \(j=i^d+1\), and let \(\Lambda\) be a spanning subgraph of \(G\) obtained from \(G_0\) by adding two edges \([i,i^d+1]\) and \([i-1,i^d]\) (see Figure 1). If there is no loop at any vertex in \(V(G)\backslash\{\frac{n+1}{2}\}\), then there is no walk of length \(n-2\) between 1 and \(n\). So \(\gamma(G)=\gamma_\Lambda(1,n)=n-1\). If \(G\) has a loop at a vertex \(m\) in \(V(P)\backslash\{\frac{n+1}{2}\}\), then there is a walk of length not more than \(2(\max\{i,m\}-1)\leqslant n-3\) from 1 to \(n\) which inserts the vertex \(m\). So \(\gamma_\Lambda(1,n)\le n-3\), and so \(\gamma(G)\leqslant \gamma(\Lambda)\leqslant n-3\).
Case 2. There is no loop at the vertex \(\frac{n+1}{2}\). Let \(u\in V(G)\backslash\{\frac{n+1}{2}\}\) be a nearest vertex with a loop to \(\frac{n+1}{2}\). Then \(1\le d(u,\frac{n+1}{2})\le \frac{n-1}{2}\).
If \(d(u,\frac{n+1}{2})=\frac{n-1}{2}\), then \(G\) has exactly two loops at the vertices \(u\) and \(u^d\). Note that \(G\) has no any other odd cycle, we conclude that \(\gamma_G(\frac{n+1}{2},\frac{n+1}{2})=2\cdot\frac{n-1}{2}=n-1\). So \(\gamma(G)=n-1\).
Now suppose that \(1\le d(u,\frac{n+1}{2})\le \frac{n-1}{2}-1\). Let \(P_1\) be a shortest path between \(u\) and \(\frac{n+1}{2}\), and let \(G_1\) be a subgraph of \(G\) obtained from \(P_1+P_1^d\) and the two loops at the end-vertices \(u\) and \(u^d\). Then \(\gamma(G_1)=2|P_1|\le n-3\). Let \(w\) be a vertex of \(G\) such that \(d(w,V(G_1))=\max\{d(x,V(G_1))\ |\ x\in V(G)\}\). Then \(1\le d(w,V(G_1))\le \frac{n-2|P_1|-1}{2}\).
If \(1\le d(w,V(G_1))\le \frac{n-2|P_1|-1}{2}-1\), then by Lemma 2.3 we have that \(\gamma(G)\le \gamma(G_1)+2d(w,V(G_1))\le n-3\).
we now assume that \(d(w,V(G_1))=\frac{n-2|P_1|-1}{2}\). Without loss of generality, we may assume \(s\in V(P_1)\) such that \(d(w,s)=d(w,V(G_1))\). Let \(P_2\) be a shortest path between \(w\) and \(s\). Then, \(G_1\cup P_2\cup P_2^d\) denoted by \(\Pi\) is a spanning subgraph of \(G\) (see Figure 2). In the following we show that \(\gamma(G)\ne n-2\).
Firstly, for every vertex \(x\) and every vertex \(y\) (not necessarily distinct) in \(V(G)\backslash\{w,w^d\}\), we have that \(\gamma_G(x,y)\le \gamma_\Pi(x,y)\le n-3\). Since there is a walk of length 2 from \(w\) to itself, we also have that \(\gamma_G(w,w)=\gamma_G(w^d,w^d)\ne n-2\).
Secondly, let \(w_1\in V(P_2)\) be a neighboring vertex of \(w\). Then for any vertex \(x\in V(G)\backslash\{w,w^d,w_1,w_1^d\}\), there is a walk of length not more than \(n-3\) from \(w\) to \(x\) which inserts the vertex \(u\). So \(\gamma_G(w,x)\le n-3\).
Thirdly, if \(d(w,\frac{n+1}{2})\le \frac{n-3}{2}\), then there is a walk of even length not more than \(n-3\) from \(w\) to \(w^d\). So \(\gamma_G(w,w^d)\ne n-2\). If \(d(w,\frac{n+1}{2})=\frac{n-1}{2}\), then \(s=u\) and \(P_1+P_2\) is a shortest path from \(w\) to \(\frac{n+1}{2}\). In this case, if \(d(w,w^d)=n-1\), then \(\gamma_G(w,w^d)=n-1\); if \(d(w,w^d)<n-1\), then there must be an edge joining a vertex \(x\in V(P_1+P_2)\) and a vertex \(y\in V(P_1^d+P_2^d)\), where \(d(y,x^d)=1\) (since \(\max\{|C|\ |\ C \text{ is an odd cycle of }G\}=1\) and \(d(w,\frac{n+1}{2})=\frac{n-1}{2}\) and there is no loop at \(\frac{n+1}{2}\)). So there is a walk of length not more than \(n-3\) from \(w\) to \(w^d\) which inserts the vertex \(u\), and so \(\gamma_G(w,w^d)\le n-3\).
Finally, if \(\gamma_G(w,x)=n-2\) for \(x\in \{w_1,w_1^d\}\), then there is no walk of length \(n-3\) from \(w\) to \(x\). Note that \(\max\{|C|\ |\ C \text{ is an odd cycle of }G\}=1\) and \(P_2\) is a shortest path between \(w\) and \(s\in V(P_1)\) with length \(|P_2|=d(w,V(G_1))\), we do have \(\gamma_G(w,w^d)=n-1\).
To sum up, we conclude that \(\gamma(G)\ne n-2\). This completes the proof of the lemma. ◻
Lemma 2.9. Let \(n\) be an odd integer with \(n\ge 5\), and let \(G\in DS(n)\). If \(\gamma(G)=n-2\), then \(G\) contains an odd cycle \(C\) with \(|C|\ge 3\), such that the vertex \(\frac{n+1}{2}\in V(C)\) and \(V(C)=V(C^d)\).
Proof. Since \(\gamma(G)=n-2\), by Lemma 2.7 and 2.8 we have that \(G\) contains an odd cycle \(C_1\) with \(|C_1|\ge 3\) and \(|V(C_1)\cap V(C_1^d)|\ge 1\).
If the vertex \(\frac{n+1}{2}\notin V(C_1)\), then \(\frac{n+1}{2}\notin V(C_1^d)\). Let \(P_1\) be a shortest path between \(\frac{n+1}{2}\) and \(w\in V(C_1)\) such that \(|P_1|=d(\frac{n+1}{2},V(C_1))\). Then \(P_1^d\) is a shortest path between \(\frac{n+1}{2}\) and \(w^d\in V(C_1^d)\), where \(w^d\ne w\). Clearly, there are two path of different parity between \(w\) and \(w^d\) in \(C_1\cup C_1^d\), which are denoted by \(P_2\) and \(\bar{P}_2\) respectively. Thus, either \(P_1+P_2+P_1^d\) or \(P_1+\bar{P}_2+P_1^d\) is an odd cycle in \(G\), and thus \(G\) contains an odd cycle \(C\) with \(|C|\ge 3\) and \(\frac{n+1}{2}\in V(C)\).
Assume that \(V(C)\ne V(C^d)\). Let \(G_1=C\cup C^d\). Then \(|V(G_1)|\ge |C|+2\). It follows from Lemma 2.3 and Lemma 2.4 that \[\gamma(G)\le \gamma(G_1)+2\cdot\frac{n-|V(G_1)|}{2}\le |C|-1+n-|V(G_1)|\le n-3,\] a contradiction.
Thus \(V(C)=V(C^d)\). The Lemma now follows. ◻
In this section, we determine the primitive doubly symmetric digraphs with the maximum scrambling index. In [5], We have obtained that \[\max\{\gamma(G)\ |\ G\in DS(n)\}=n-1.\]
By \(k(G)=\left\lceil\frac{\gamma(G)}{2}\right\rceil\) [7] and (1), we have that \(\max\{k(G)\ |\ G\in DS(n)\}=\left\lceil\frac{n-1}{2}\right\rceil\) if and only if \(\gamma(G)=n-1\), or \(\gamma(G)=n-2\) and \(n\equiv 1(\mathrm{mod}\ 2)\). Since the extremal digraphs for the case \(\gamma(G)=n-1\) are already settled in [6], we will only characterize the remaining case \(\gamma(G)=n-2\) and \(n\equiv 1(\mathrm{mod}\ 2)\). The following theorem is obvious.
Theorem 3.1. Let \(\triangle^\circ=(V,E)\) be a graph of order 3, where \(V=\{1,2,3\}\) and \(E=\{[1,2],[2,3],[3,1],[1,1],[2,2],[3,3]\}\). Let \(G\in DS(3)\). Then \(\gamma(G)=1\) if and only if \(G\) is isomorphic to \(\triangle^\circ\).
Now let \(n\) be an odd integer with \(n\geqslant 5\), and let \(s\) be an integer with \(1\leqslant s\leqslant \frac{n-1}{2}\). Let \(\Omega^{(0)}=(V,E)\), where \(V=\{1,2,\cdots,n\}\) and \(E=\{[i,i+1]|1\le i\le n-1\}\cup\{[s,n+1-s]\}\). Let \(\Omega_n\) denote any graph that can be obtained from \(\Omega^{(0)}\) by adding two loops \([\frac{n-1}{2},\frac{n-1}{2}]\) and \([\frac{n+3}{2},\frac{n+3}{2}]\), and possibly by adding some edges of the form \([i,i^d]\), where \(s+1\leqslant i\leqslant \frac{n+1}{2}\). Clearly, \(\Omega_n\subset DS(n)\). The set of graphs \(\Omega_n\) is shown in Figure 3.
Theorem 3.2. Let \(n\) be an odd integer with \(n\ge 5\), and let \(G\in DS(n)\). Then \(\gamma(G)=n-2\) if and only if \(G\) is isomorphic to some graph in \(\Omega_n\).
Proof. Let \(G\in \Omega_n\) and let \(u\) be any vertex of \(G\). Then \[\gamma_G(v,u)\le n-3 \text{ for } 2\le v\le n-1;\] \[\gamma_G(1,1)=\gamma_G(n,n)\le n-3;\] \[\gamma_G(1,u)=\gamma_G(n,u^d)\le \gamma_G(1,n)=n-2.\]
Thus, \(\gamma(G)=\gamma_G(1,n)=n-2\).
On the other hand, suppose that \(\gamma(G)=n-2\). Let \(u,v\in V(G)\) such that \(\gamma(u,v)=\gamma(G)=n-2\). Then \(u\ne v\) since \(n-2\) is an odd integer. By Lemma 2.9, there is an odd cycle \(C\) with \(|C|\ge 3\), such that the vertex \(\frac{n+1}{2}\in V(C)\) and \(V(C)=V(C^d)\). Without loss of generality, we may assume \(C\) is the largest such odd cycle. Then \(d(u,V(C))=d(v,V(C))=\frac{n-|C|}{2}\) and \(v=u^d\). Let \(P\) be a shortest path between \(u\) and \(s\in V(C)\) such that \(|P|=d(u,V(C))\). Then \(P^d\) is a shortest path between \(u^d\) and \(s^d\in V(C)\).
Assume that \(s=s^d\) or \(|Q_C(s,s^d)|\geqslant 2\). Then there is a walk of even length not more than \(n-3\) between \(u\) and \(u^d\). This contradicts \(\gamma_G(u,u^d)=n-2\).
Thus \(|Q_C(s,s^d)|=1\), and thus \(G\) contains a spanning subgraph \(G^*\) isomorphic to \(\Omega_n^{(0)}\). For convenience, let \(G^*=\Omega^{(0)}\). This implies that \(u=1\) and \(|C|=n-2(s-1)\). Since \(\gamma(\Omega^{(0)})=\gamma_{\Omega^{(0)}}(1,n)=n-1\), there must be an edge \([i,j]\in E(G)\backslash E(\Omega^{(0)})\).
Assume that \(|j-i|=1\). Then \(G\) contains multiple edges, a contradiction.
Assume that \(|j-i|\ge 2\) and \(j\ne i^d\). Notices that \([i^d,j^d]\in E(G)\) and \(P+C\backslash Q_C(s,s^d)+P^d\) is a path in \(G\) from 1 to \(n\) of length \(n-1\). Then there is a walk of even length not more than \(n-3\) between 1 and \(n\). This contradicts \(\gamma_G(1,n)=n-2\).
Thus \(j=i^d\) or \(j=i\). If all the edges in \(E(G)\backslash E(\Omega^{(0)})\) are of the form \([i,i^d]\) (in particular, \([i,i^d]\) is a loop when \(i=\frac{n+1}{2}\)), then there is still \(\gamma_G(1,n)=n-1\). Thus, there must be an edge of the form \([i,i]\) in \(E(G)\backslash E(\Omega^{(0)})\); that is, there must be a loop at \(i\) (and so there is also a loop at \(i^d\)).
Assume that \(1\le i\le \frac{n-3}{2}\). Then there is a walk of even length not more than \(n-3\) between 1 and \(n\). This contradicts \(\gamma_G(1,n)=n-2\).
Thus \(i=\frac{n-1}{2}\), and thus there are two loops in \(G\) at the vertices \(\frac{n-1}{2}\) and \(\frac{n+3}{2}\). Since \(C\) is the largest odd cycle in \(G\) such that the vertex \(\frac{n+1}{2}\in V(C)\) and \(V(C)=V(C^d)\), the existence of an edges of the form \([i,i^d]\) in \(G\) implies that \(s+1\leqslant i\leqslant \frac{n+1}{2}\).
Therefore \(G\in \Omega_n\). The theorem now follows. ◻
Research supported by NNSF of China (No.11571101) and NSF of Hunan Province (No. 2016JJ2051).