The kth Local Exponent of Doubly Symmetric Primitive Digraphs with d Loops

Abstract

Let D be a primitive digraph of order $n.$ The exponent of a vertex x in $V(D)$ is denoted ${\gamma }_D(x),$ which is the smallest integer q such that for any vertex $y,$ there is a walk of length q from x to y. Let $V(D)=\{v_1,v_2,\cdots ,v_n\}.$ We order the vertices of $V(D)$ so that ${\gamma }_D(v_1)\le {\gamma }_D(v_2)\le \cdots \le {\gamma }_D(v_n)$ is satisfied. Then, for any integer k satisfying $1\le k\le n$, ${\gamma }_D(v_k)$ is called the kth local exponent of D and is denoted by $ex{p}_D(k).$ Let $D{S}_n(d)$ represent the set of all doubly symmetric primitive digraphs with n vertices and d loops, where d is an integer such that $1\le d\le n.$ In this paper, we determine the upper bound for the kth local exponent of $D{S}_n(d)$, where $1\le k\le n.$ In addition, we find that the upper bound for the kth local exponent of $D{S}_n(d)$ can be reached, where $1\le k\le n.$

1. Introduction

Let $D=(V,E)$ denote a digraph (directed graph) with n vertices, where the vertex set $V=V(D)$ and the arc set $E=E(D).$ Loops are permitted, but multiple arcs are not. A walk from x to y in $D,$ we mean a sequence of vertices $x,v_1,\cdots ,v_t,y$ where each vertex in the sequence of vertices belongs to $V,$ and a sequence of arcs $(x,v_1),(v_1,v_2),\cdots ,(v_t,y)$ where each arc in the sequence of arcs belongs to $E,$ and the vertices and arcs are not necessarily distinct. The number of arcs in W is the length of the walk $W.$ The notation $x\stackrel{k}{\to }y$ means that there exists a walk of length k from x to $y.$ The distance from vertex x to vertex y in D is written as $d_D(x,y)$(for short, $d(x,y)$), which refers to the length of the shortest walk from x to $y.$ If $x=y,$ then a walk from x to y is a closed walk. A cycle is a closed walk from x to y with distinct vertices except for $x=y.$

Let $x,y$ be any pair of vertices in a digraph $D.$ The digraph D is called primitive, if there exists a positive integer k such that there is a walk of length k from x to $y.$ This smallest such k is denoted by $exp(D),$ which is called the exponent of $D.$ The greatest common divisor of the lengths of all the cycles in D is recorded as $l(D).$ It is well known (see [1]) that D is primitive if and only if D is strongly connected and $l(D)=1.$

Brualdi and Liu [2] generalized the concept of exponent for a primitive digraph (primitive matrix). Let D be a primitive digraph with n vertices. The exponent of D can be broken down into more local exponents [3]. For any pair of vertices $x,z\in V(D),$ let ${\gamma }_D(x,z)$ denote the smallest integer p such that there is a walk of length t from x to z, for each integer $t\ge p.$ Since D is a primitive digraph, then ${\gamma }_D(x,z)$ is a finite number. For any vertex $x\in V(D),$ the exponent of vertex x is written as ${\gamma }_D(x),$ which is the smallest integer q so that for any vertex $y\in V(D),$ there exists a walk of length q from x to $y.$ Moreover, for any vertex $z\in V(D)$ and any integer $t\ge {\gamma }_D(x,z),$ there is a walk of length t from x to $z.$ So, we have $q=max\{{\gamma }_D(x,z):z\in V(D)\}.$ Then, for any vertex $y\in V(D),$ there is a walk of length t from x to y for each integer $t\ge q.$ Therefore, we have

$${\gamma }_D(x)=max\{{\gamma }_D(x,z):z\in V(D)\}.$$

Let the vertices of D be ordered as $v_1,v_2,\cdots ,v_n$ such that

$${\gamma }_D(v_1)\le {\gamma }_D(v_2)\le \cdots \le {\gamma }_D(v_n).$$

${\gamma }_D(v_k)$ is called the kth local exponent (generalized exponent) of $D,$ and it is denoted by $ex{p}_D(k),$ where $1\le k\le n.$ Then,

$$ex{p}_D(1)\le ex{p}_D(2)\le \cdots \le ex{p}_D(n).$$

Furthermore, we have $\gamma (D)=max\{{\gamma }_D(x):x\in V(D)\}=max\{{\gamma }_D(x,y):x,y\in V(D)\}.$ Obviously, the exponent of D equals $ex{p}_D(n).$ That is, $\gamma (D)=exp(D)=ex{p}_D(n).$ So, for a primitive digraph $D,$ the local exponents of D are generalizations of the exponent of $D.$

Brualdi and Liu [2] proposed a memoryless communication system. In the memoryless communication system represented by a primitive digraph D of order $n,$ the kth local exponent is the smallest time for each vertex to simultaneously hold all k bits of the information. For more details, please refer to [2,3].

For any vertices x and y of a digraph $D$, $(x,y)\in E(D)$ is an arc if and only if $(y,x)\in E(D)$ is an arc, which is represented by $x\leftrightarrow y,$ then such a digraph D is called a symmetric digraph. An undirected graph (possibly with loops) can be viewed as a symmetric digraph. For some research on undirected graphs, please see [4,5,6]. When D is symmetric, the notation $x\stackrel{k}{\to }y$ indicates that there is a walk of length k from x to $y.$

Let $D=(V,E)$ be a symmetric digraph, we can regard D as an undirected graph. For convenience, undirected graph terms such as edges, edge set, etc., are used directly to describe a symmetric digraph. Then, let $E(D)$ denote the set of undirected edges (edges) in $D.$ Moreover, we assume that the notation $\left[x,y\right]\in E(D)$ represents that there is an edge in D with $x,y$ as end vertices.

Let $D=(V,E)$ be a symmetric digraph, where $V=\{v_1,v_2,\cdots ,v_n\}.$ If for any vertices $v_i$ and $v_j$, $[v_i,v_j]\in E(D)$ if and only if $[v_{n+1-i},v_{n+1-j}]\in E(D)$, then such a symmetric digraph D is called a doubly symmetric digraph. Moreover, $[v_i,v_j]$ and $[v_{n+1-i},v_{n+1-j}]$ are called a pair of symmetrical edges, or $[v_i,v_j]$ is a symmetrical edge of $[v_{n+1-i},v_{n+1-j}],$ where $1\le i\le n$ and $1\le j\le n.$ The vertices $v_{n+1-i}$, $v_i$ are called a pair of symmetric vertices, or $v_i$ is a symmetric vertex of $v_{n+1-i},$ where $1\le i\le n.$ According to this definition, when n is odd, $v_{\frac{n+1}{2}}$ is symmetric to itself. If $v_i$ is a loop vertex, then $[v_i,v_i]\in E(D)$ and $[v_{n+1-i},v_{n+1-i}]\in E(D).$ Therefore, for $i\ne n+1-i,$ if $[v_i,v_i]$ is a loop, then $[v_{n+1-i},v_{n+1-i}]$ is also a loop, the loops appear in pairs. A doubly symmetric digraph D is called a doubly symmetric primitive digraph provided D is primitive.

If a doubly symmetric primitive digraph D contains exactly d loops, then we call D a doubly symmetric primitive digraph with d loops. Let $D{S}_n$ denote the set of all doubly symmetric primitive digraphs of order n. Let $D{S}_n(d)$ denote the set of all doubly symmetric primitive digraphs of order n with d loops, where d is an integer such that $1\le d\le n.$ Obviously, we have $D{S}_n(d)\subseteq D{S}_n.$

Let $D\in D{S}_n(d).$ After deleting any pair of symmetrical edges $[v_i,v_j]$ and $[v_{n+1-i},v_{n+1-j}]$ of $D,$ the obtained digraph $D^{\prime }$ is not a doubly symmetric primitive digraph (that is, $D^{\prime }$ is not connected), then we call $D\in D{S}_n^{\prime }(d),$ where $1\le i<j\le n.$ Obviously, we have $D{S}_n^{\prime }(d)\subseteq D{S}_n(d).$

For example, we consider the kth local exponent of the graph $G.$ Let $V(G)=\{v_1,v_2,\cdots$, $v_7\}.$ Let $E(G)=\left\{[v_i,v_{i+1}]\right|1\le i\le 6\}\cup \left\{[v_4,v_4]\right\}.$G is shown in Figure 1.

We easily get ${\gamma }_G(v_4)=3$, ${\gamma }_G(v_3)={\gamma }_G(v_5)=4$, ${\gamma }_G(v_2)={\gamma }_G(v_6)=5$, ${\gamma }_G(v_1)={\gamma }_G(v_7)=6.$ Then, we have $ex{p}_G(1)=3,ex{p}_G(2)=ex{p}_G(3)=4,ex{p}_G(4)=ex{p}_G(5)=5,ex{p}_G(6)=ex{p}_G(7)=6.$ Moreover, we have $\gamma (G)=exp(G)=ex{p}_G(7)=6.$

Some studies [7,8,9,10,11,12] have investigated exponents and their generalization. Chen and Liu [11] studied the kth local exponent of doubly symmetric primitive matrices (primitive digraphs). Chen and Liu [12] characterized the doubly symmetric primitive digraphs with the kth local exponent reaching the maximum value. A doubly symmetric primitive digraph with d loops is a special doubly symmetric primitive digraph. It is important to mention that the kth local exponent of such a class of digraphs has not been studied before. Using graph theory methods, we obtain the upper bound of the kth local exponent of digraphs in $D{S}_n(d),$ where $1\le k\le n.$ Some studies have investigated the scrambling index [13,14,15,16] and generalized competition index [17,18,19,20,21,22,23]. Several studies explored the generalized $\mu$-scrambling indices, please refer to [24,25,26].

Let $D\in D{S}_n(d).$ Let $V(L(D))$ represent the set of d loop vertices in $D.$ Let $E(L(D))$ denote the set of d loops in $D.$ Let $v_i$, $v_j$ be any pair of vertices of the digraph $D.$ If the walk from $v_i$ to $v_j$ in D is denoted as $W_D(v_i,v_j)$ (for short, $W(v_i,v_j)$), then $|W(v_i,v_j)|$ is used to denote the length of the walk $W(v_i,v_j)$, and $V(W(v_i,v_j))$ is used to denote the set of all vertices in this walk $W(v_i,v_j).$ If there is a unique path from $v_i$ to $v_j$ in $D,$ then let $P_D(v_i,v_j)$ (for short, $P(v_i,v_j)$) denote the unique path, and let $V(P_D(v_i,v_j))$ (for short, $V(P(v_i,v_j))$) denote the set of all vertices on the path. If $v_i=v_j,$ then $V(P(v_i,v_j))=\left\{v_i\right\}=\left\{v_j\right\}.$ If a walk $W(v_i,v_j)$ from $v_i$ to $v_j$ in D does not pass through a loop vertex, then let $V(W(v_i,v_j))\cap V(L(D))=\varnothing ,$ otherwise $V(W(v_i,v_j))\cap V(L(D))\ne \varnothing .$ Similarly, if the unique path from $v_i$ to $v_j$ passes through a loop vertex, that is $V(P(v_i,v_j))\cap V(L(D))\ne \varnothing ,$ otherwise $V(P(v_i,v_j))\cap V(L(D))=\varnothing .$

For a vertex $v\in V(D)$ and a set $X\subseteq V(D),$ let $d(v,X)=min\{d(v,v_i):v_i\in X\}.$ If $v\in X,$ let $d(v,X)=0.$ For any vertex $u\in V(D)$ and $v\in V(D),$ if $u=v,$ let $d(u,v)=0.$ If T is a set, the notation $\left|T\right|$ is used to denote the number of all elements in $T.$ The notation $⌊a⌋$ is used to denote the largest integer not greater than $a,$ and the notation $⌈b⌉$ is used to denote the smallest integer not less than $b.$

In this paper, let $n,d$ and k be integers with $n\ge 5$, $1\le k\le n,1\le d\le n.$ We give the upper bound of the kth local exponent of digraphs in $D{S}_n(d),$ where $1\le k\le n.$

2. The Upper Bound for the $\mathit{k}$th Local Exponent of ${\mathit{DS}}_{\mathit{n}}(\mathit{d})$

In this section, let $D=(V,E),$ where $V=\{v_1,v_2,\cdots ,v_n\}.$

In the case of $D\in D{S}_n(d)$, we observe the exponent of any vertex in $D,$ it is easy to get the following Proposition 1, let us omit the proof.

Proposition 1.

Let $D\in D{S}_n(d)$ and let $v_i$ be any vertex of $D,$ then ${\gamma }_D(v_i)={\gamma }_D(v_{n+1-i}),$ where $1\le i\le n.$

Lemma 1

(Lemma 3.3 [2]). Let D be a primitive digraph with n vertices. Then, $ex{p}_D(k+1)\le ex{p}_D(k)+1,$ where $1\le k\le n-1.$

Remark 1.

Lemma 1 is actually very useful. Next, we repeat the proof of Brualdi and Liu (see [2]). Since D is strongly connected, for any integer k such that $1\le k\le n-1,$ there is a vertex x that is joined by an arc to one of the vertices with the k smallest exponents. Therefore, $ex{p}_D(k+1)\le ex{p}_D(k)+1,$ where $1\le k\le n-1.$

Lemma 2.

Let $D\in D{S}_n(d)$ and let $v_i,v_j$ be any pair of vertices of $D.$ Then, ${\gamma }_D(v_j)\le {\gamma }_D(v_i)+d(v_i,v_j).$

Proof. 

For any vertex $x\in V(D),$ there is a walk of length t from $v_i$ to x, which is $v_i\stackrel{t}{\to }x,$ for each integer $t\ge {\gamma }_D(v_i).$ So, there is a walk of length s from $v_j$ to x, which is $v_j\stackrel{d(v_j,v_i)}{\to }{v}_i\stackrel{t}{\to }x,$ for each integer $s\ge {\gamma }_D(v_i)+d(v_i,v_j).$ Therefore, ${\gamma }_D(v_j)\le {\gamma }_D(v_i)+d(v_i,v_j).$ □

Lemma 3.

Let $D\in D{S}_n(d)$ and let $x,y$ be any pair of vertices of $D.$ If there exists a walk $W(x,y)$ from x to y such that $V(W(x,y))\cap V(L(D))\ne \varnothing ,$ then ${\gamma }_D(x,y)\le \left|W(x,y)\right|.$

Proof. 

Let $h=|W(x,y)|.$ We consider the following.

Case 1 $x\in V(D)\backslash V(L(D))$ and $y\in V(D)\backslash V(L(D)).$

Suppose a walk from x to y through a loop vertex is denoted by $x\stackrel{a}{\to }{v}_i\stackrel{h-a}{\to }y,$ where $v_i$ is a loop vertex and a is an integer such that $1\le a\le h-1.$ Then, the length of the walk $x\stackrel{a}{\to }{v}_i\stackrel{1}{\to }{v}_i\stackrel{h-a}{\to }y$ is $h+1.$ The length of the walk $x\stackrel{a}{\to }{v}_i\stackrel{1}{\to }{v}_i\stackrel{1}{\to }{v}_i\stackrel{h-a}{\to }y$ is $h+2.$ Similarly, we can easily conclude that there is a walk of length s from x to y, for each integer $s\ge h.$ So, ${\gamma }_D(x,y)\le \left|W(x,y)\right|.$

Case 2 $x\in V(L(D))$ or $y\in V(L(D)).$

Similar to Case 1, it is easy to get that there is a walk of length s from x to y, for each integer $s\ge h.$ So, ${\gamma }_D(x,y)\le \left|W(x,y)\right|.$

Therefore, the lemma holds. □

Lemma 4

(Lemma 1 [23]). Let $D\in D{S}_n.$ If n is odd and x is any vertex of D, then $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$

Theorem 1.

Let $D\in D{S}_n(d).$ If n is odd and d is odd, then $ex{p}_D(k)\le \frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

Proof. 

If d is odd, then $v_{\frac{n+1}{2}}$ is a loop vertex. Let x be any vertex. Then, a shortest path from x to $v_{\frac{n+1}{2}}$ goes through the loop vertex $v_{\frac{n+1}{2}}.$ According to Lemma 4, we have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Furthermore, according to Lemma 3, we have ${\gamma }_D(v_{\frac{n+1}{2}},x)\le d(x,v_{\frac{n+1}{2}}).$ Further, we have ${\gamma }_D(v_{\frac{n+1}{2}},x)=d(x,v_{\frac{n+1}{2}}).$ So, ${\gamma }_D(v_{\frac{n+1}{2}})=max\{d(v_{\frac{n+1}{2}},x):x\in V(D)\}\le \frac{n-1}{2}.$ Then, we have $ex{p}_D(1)\le {\gamma }_D(v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Further, according to Proposition 1, we have ${\gamma }_D(v_1)={\gamma }_D(v_n),{\gamma }_D(v_2)={\gamma }_D(v_{n-1}),\cdots ,{\gamma }_D(v_{\frac{n-1}{2}})={\gamma }_D(v_{\frac{n+3}{2}}).$ So, according to Lemma 1, we conclude $ex{p}_D(2)=ex{p}_D(3)\le ex{p}_D(1)+1\le \frac{n-1}{2}+1,$$ex{p}_D(4)=ex{p}_D(5)\le ex{p}_D(1)+2\le \frac{n-1}{2}+2,\cdots ,ex{p}_D(n-1)=ex{p}_D(n)\le ex{p}_D(1)+\frac{n-1}{2}\le \frac{n-1}{2}+\frac{n-1}{2}.$ Therefore, we have $ex{p}_D(k)\le ex{p}_D(1)+⌊\frac{k}{2}⌋\le \frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$ □

Let $D^{\prime }\in D{S}_n(d)$ and $D\in D{S}_n(d).$ If D is a subgraph of $D^{\prime }$ such that $V(D)=V(D^{\prime })$ and $E(D)\subseteq E(D^{\prime }),$ then $ex{p}_{D^{\prime }}(k)\le ex{p}_D(k),$ where $1\le k\le n.$ So, if we investigate the upper bound of the kth local exponent of digraphs in $D{S}_n(d),$ we only need to investigate the digraphs in $D{S}_n^{\prime }(d).$

Referring to Definition 3 in [23], we give the following Definition 1.

Definition 1.

Let $D\in D{S}_n^{\prime }(d),$ where n is odd, d is even such that $d\ge 2.$ There exist two connected subgraphs $D_{*}=(V_{*},E_{*})$ and $D_{**}=(V_{**},E_{**})$ of $D,$ and $D_{*},D_{**}$ satisfy $V(D)=V_{*}\cup V_{**}$ and $E(D)=E_{*}\cup E_{**}\cup E(L(D)).$ Where $V_{*}=\{v_{n+1-i}:v_i\in V_{**}\}$ and $E_{*}=\{[v_{n+1-i},v_{n+1-j}]:[v_i,v_j]\in E_{**}\}.$ Moreover,$|V_{*}|=|V_{**}|=\frac{n+1}{2},|E_{*}|=|E_{**}|=\frac{n-1}{2}.$

Remark 2.

Suppose n is odd and d is even that satisfies $d\ge 2.$ If $D\in D{S}_n^{\prime }(d),$ then there are two connected subgraphs $D_{*}$ and $D_{**}$ of $D.$ In addition, there is a unique path for any two different vertices in $D_{*}$ and $D_{**},$ respectively. Moreover, there is a unique path for any two different vertices in $D.$ Let $x,y$ be any pair of vertices of D such that $x\in V_{*}$ and $y\in V_{**},$ then $V(P(x,v_{\frac{n+1}{2}}))\cap V(P(v_{\frac{n+1}{2}},y))=\{v_{\frac{n+1}{2}}\}$ (see [23]). After removing d loops from $D,$ the obtained graph is a tree. Therefore, D is a special tree with loops that satisfies $[v_i,v_j]\in E(D)$ if and only if $[v_{n+1-i},v_{n+1-j}]\in E(D)$, where $1\le i<j\le n.$

Lemma 5

(Lemma 3 [23]). Let $D\in D{S}_n^{\prime }(d),$ where n is odd, d is even such that $d\ge 2.$ Let $x,y$ be any pair of vertices of D such that $V(P(x,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing$ and $V(P(y,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing .$ Then, there is a walk $W(x,y)$ from x to y such that $V(W(x,y))\cap V(L(D))\ne \varnothing ,$ and $|W(x,y)|\le n-d+1.$

Corollary 1.

Let $D\in D{S}_n^{\prime }(d),$ where n is odd, d is even and $d\ge 2.$ Let $x,y$ be any pair of vertices of D satisfying $V(P(x,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing$ and $V(P(y,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing .$ Then, ${\gamma }_D(x,y)\le n-d+1.$

Proof. 

According to Lemma 5, there is a walk $W(x,y)$ from x to y passing through a loop vertex, and $|W(x,y)|\le n-d+1.$ Moreover, according to Lemma 3, we have ${\gamma }_D(x,y)\le \left|W(x,y)\right|\le n-d+1.$ □

In Corollary 1, if $x=v_{\frac{n+1}{2}}$ and x isn’t a loop vertex, then $V(P(x,v_{\frac{n+1}{2}}))=\{v_{\frac{n+1}{2}}\},$ we have $V(P(x,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing .$

Theorem 2.

Let $D\in D{S}_n(d).$ If n is odd, d is even and $d\ge 2,$ then

(1)

If $n\le 2d-3,$ then $ex{p}_D(k)\le \frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

(2)

If $n\ge 2d-1,$ then

$$ex{p}_D(k)\le \left\{\begin{array}{cc}n-d+1,\hfill & \mathit{where}1\le k\le n-2d+4,\hfill \\ n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,\hfill & \mathit{where}n-2d+4\le k\le n.\hfill \end{array}\right.$$

Proof. 

We only need to consider $D\in D{S}_n^{\prime }(d).$ Since d is even, then $v_{\frac{n+1}{2}}$ isn’t a loop vertex. Let x be any vertex. By Lemma 4, we have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ If the path from $v_{\frac{n+1}{2}}$ to x passes through a loop vertex, that is $V(P(v_{\frac{n+1}{2}},x))\cap V(L(D))\ne \varnothing ,$ then ${\gamma }_D(v_{\frac{n+1}{2}},x)=d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ If vertex x satisfies $V(P(v_{\frac{n+1}{2}},x))\cap V(L(D))=\varnothing ,$ according to Corollary 1, we have ${\gamma }_D(v_{\frac{n+1}{2}},x)\le n-d+1.$ Therefore, we have ${\gamma }_D(v_{\frac{n+1}{2}})\le max\{\frac{n-1}{2},n-d+1\}.$

(1)

If $n\le 2d-3,$ then $n-d+1\le \frac{n-1}{2}.$ Then, we have $ex{p}_D(1)\le {\gamma }_D(v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ According to Proposition 1, we have ${\gamma }_D(v_1)={\gamma }_D(v_n),{\gamma }_D(v_2)={\gamma }_D(v_{n-1}),\cdots ,{\gamma }_D(v_{\frac{n-1}{2}})$$={\gamma }_D(v_{\frac{n+3}{2}}).$ Then, according to Lemma 1, we can conclude that $ex{p}_D(2)=ex{p}_D(3)\le ex{p}_D(1)+1\le \frac{n-1}{2}+1,$$ex{p}_D(4)=ex{p}_D(5)\le ex{p}_D(1)+2\le \frac{n-1}{2}+2,$$\cdots .$ Therefore, we have $ex{p}_D(k)\le ex{p}_D(1)+⌊\frac{k}{2}⌋\le \frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

(2)

If $n\ge 2d-1,$ then $n-d+1\ge \frac{n+1}{2}.$ We have $ex{p}_D(1)\le {\gamma }_D(v_{\frac{n+1}{2}})\le n-d+1.$

Next, we construct a set $V(M)$ such that $|V(M)|\ge n-2d+4,$ and for any vertex $v_i\in V(M),$${\gamma }_D(v_i)\le n-d+1$ holds. Suppose $V(M)=\{v:d(v,v_{\frac{n+1}{2}})\le \frac{n-2d+3}{2}\}.$ Then, $v_{\frac{n+1}{2}}\in V(M).$

Suppose $v_h\in V(M)$$\cap V_{*}$ and $v_h\ne v_{\frac{n+1}{2}}.$ If the vertex sequence of the unique path in $D_{*}$ from $v_h$ to $v_{\frac{n+1}{2}}$ is $v_h,\cdots ,v_t,\cdots ,v_{\frac{n+1}{2}},$ then the vertex sequence of the unique path in $D_{**}$ from $v_{n+1-h}$ to $v_{\frac{n+1}{2}}$ is $v_{n+1-h},\cdots ,v_{n+1-t},\cdots ,v_{\frac{n+1}{2}}.$ Moreover, $V(P(v_h,v_{\frac{n+1}{2}}))\cap V(P(v_{n+1-h},v_{\frac{n+1}{2}}))=\{v_{\frac{n+1}{2}}\}.$ So, $d(v_h,v_{\frac{n+1}{2}})=d(v_{n+1-h},v_{\frac{n+1}{2}})\le \frac{n-2d+3}{2}.$ Therefore, we have $v_{n+1-h}\in V(M).$ Next, we prove that $|V(M)|\ge n-2d+4.$ For any vertex $v_s\in V(D),$ if $v_s\in V(M),$ then $|V(M)|=n.$ If there is a vertex $v_l$ satisfying $v_l\in V(D)\backslash V(M)$, then $d(v_l,v_{\frac{n+1}{2}})\ge \frac{n-2d+3}{2}+1.$ So, $V(P(v_l,v_{\frac{n+1}{2}}))\cap V(M)=\frac{n-2d+3}{2}+1.$ Moreover, $V(P(v_{n+1-l},v_{\frac{n+1}{2}}))\cap V(M)=\frac{n-2d+3}{2}+1$ and $V(P(v_l,v_{\frac{n+1}{2}}))\cap V(P(v_{n+1-l},v_{\frac{n+1}{2}}))=\{v_{\frac{n+1}{2}}\}.$ Then, we have $|\left(V(P(v_l,v_{\frac{n+1}{2}}))\cup V(P(v_{n+1-l},v_{\frac{n+1}{2}}))\right)\cap V(M)|=n-2d+4.$ Therefore, we have $|V(M)|\ge n-2d+4.$ For any vertex $v_i\in V(M),$ next we consider ${\gamma }_D(v_i).$

For any vertex $v_i\in V(M),$ let the walk $V(W(v_i,x))$ from $v_i$ to x be $v_i\stackrel{d(v_i,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}\stackrel{d(v_{\frac{n+1}{2}},x)}{\to }x.$ If the walk $V(W(v_i,x))$ passes through a loop vertex, we have ${\gamma }_D(v_i,x)\le d(v_i,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},x)\le \frac{n-2d+3}{2}+\frac{n-1}{2}=n-d+1.$ If the walk $V(W(v_i,x))$ doesn’t pass through a loop vertex, that is, $V(W(v_i,x))\cap V(L(D))=\varnothing .$ Then, we have $V(P(v_i,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing$ and $V(P(x,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing .$ So, if $V(W(v_i,x))\cap V(L(D))=\varnothing ,$ according to Corollary 1, we have ${\gamma }_D(v_i,x)\le n-d+1.$ Therefore, we have ${\gamma }_D(v_i)\le n-d+1.$ According to Proposition 1, we have ${\gamma }_D(v_{n+1-i})={\gamma }_D(v_i)\le n-d+1.$ Therefore, we have $ex{p}_D(k)\le n-d+1,$ where $1\le k\le |V(M)|.$

For any vertex $v_j$ such that $v_j\in V(D)\backslash V(M)$, then $v_{n+1-j}\in V(D)\backslash V(M).$ There is a unique path for any pair of vertices in $D.$ So for any vertex $v_i\in V(M),$ we have $d(v_j,v_i)=d(v_{n+1-j},v_{n+1-i}).$ Suppose $d(v_j,V(M))=d(v_j,v_l),$ where $v_l\in V(M).$ We have $d(v_{n+1-j},v_{n+1-l})=d(v_j,v_l)\le d(v_j,v_i)=d(v_{n+1-j},v_{n+1-i}).$ So, we have $d(v_j,V(M))=d(v_{n+1-j},V(M)).$ Furthermore, according to Lemma 2, we can easily conclude that ${\gamma }_D(v_j)={\gamma }_D(v_{n+1-j})\le n-d+1+d(v_j,V(M)).$ Since $|V(M)|\ge n-2d+4,$ the conclusion is clearly established.

Therefore, the theorem holds. □

Referring to Definition 4 in [23], we give the following Definition 2.

Definition 2.

Let $D\in D{S}_n^{\prime }(d),$ where n is even, d is even such that $d\ge 2.$

(1)

There exist two connected subgraphs $D_1=(V_1,E_1)$ and $D_2=(V_2,E_2)$ of $D,$ and $D_1,D_2$ satisfy $V(D)=V_1\cup V_2$ and $E(D)=E_1\cup E_2\cup \left\{[v_f,v_{n+1-g}]\right\}\cup \left\{[v_{n+1-f},v_g]\right\}\cup E(L(D)).$ Where $V_1=\{v_{n+1-i}:v_i\in V_2\}$ and $E_1=\{[v_{n+1-i},v_{n+1-j}]:[v_i,v_j]\in E_2\},$$v_f\in V_1$ and $v_g\in V_1.$ Moreover,$|V_1|=|V_2|=\frac{n}{2},|E_1|=|E_2|=\frac{n}{2}-1.$

(2)

If $\{v_f,v_{n+1-f}\}\cap V(L(D))=\varnothing .$ Let $V(H_1)=\{v:V(P_{D_1}(v_f,v))\cap V(L(D))=\varnothing ,\mathit{where}v\in V_1\}$ and $V(H_2)=\{v:V(P_{D_2}(v_{n+1-f},v))\cap V(L(D))=\varnothing ,\mathit{where}v\in V_2\}.$ Suppose $V(H)=V(H_1)\cup V(H_2).$

Definition 3.

Let $D\in D{S}_n^{\prime }(d),$ where n is even, d is even such that $d\ge 2.$ In Definition 2(1), we give the following definition:

(1)

Let $W(v_f,v_f)$ be $v_f\stackrel{d_{D_1}(v_f,v_g)}{\to }{v}_g\stackrel{d_D(v_g,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_{D_2}(v_{n+1-f},v_{n+1-g})}{\to }{v}_{n+1-g}$

$\stackrel{d_D(v_{n+1-g},v_f)}{\to }{v}_f,$ then $W(v_f,v_f)$ is a closed walk from $v_f$ to $v_f.$ Let us write $V(W(v_f,v_f))=V(R).$

(2)

If $f\ne g,$ let $D\in D{S}_{n,1}^{\prime }(d).$ If $f=g,$ let $D\in D{S}_{n,2}^{\prime }(d).$

Remark 3.

Suppose n is even and d is even that satisfies $d\ge 2.$ If $D\in D{S}_n^{\prime }(d),$ then there are two connected subgraphs $D_1$ and $D_2$ of $D.$ Moreover, there is a unique path for any two different vertices in $D_1$ and $D_2,$ respectively. Since D is connected, then there are edges $[v_f,v_{n+1-g}]\in E(D)$ and $[v_{n+1-f},v_g]\in E(D).$ Then, $d_D(v_g,v_{n+1-f})=d_D(v_{n+1-g},v_f)=1.$ If $v_f$ and $v_{n+1-f}$ are not loop vertices, then $v_f\in V(H)$ and $v_{n+1-f}\in V(H).$ If $D\in D{S}_{n,1}^{\prime }(d),$ then $f\ne g$, and $|V(R)|$ is even such that $|V(R)|\ge 4.$ Furthermore, if $D\in D{S}_{n,1}^{\prime }(d),$ after removing d loops from $D,$ the obtained graph $D^{*}$ is not a tree. According to Definitions 2 and 3, it is not difficult to see that $|V(D^{*})|=n$ and $|E(D^{*})|=n.$ If $D\in D{S}_{n,2}^{\prime }(d),$ then $f=g$, $V(R)=\{v_f,v_{n+1-f}\}$ and $|V(R)|=2.$ If $D\in D{S}_{n,2}^{\prime }(d),$ then D is a special tree with loops that satisfies $[v_i,v_j]\in E(D)$ if and only if $[v_{n+1-i},v_{n+1-j}]\in E(D)$, where $1\le i<j\le n.$ In fact, $D\in D{S}_{n,2}^{\prime }(d)$ can be regarded as a special case of $f=g$ in $D\in D{S}_{n,1}^{\prime }(d).$

In Lemma 2 in [23], let $D\in D{S}_n^{\prime }(d),$ where n is even and d be even such that $d\ge 2.$ We can directly get the following Lemma 6.

Lemma 6.

Let $D\in D{S}_n^{\prime }(d).$ Let n be even and d be even such that $d\ge 2.$ Let x be any vertex of $D.$ Then, for any vertex $v_s\in V(R),$ we have $d(x,v_s)\le \frac{n}{2}.$

Lemma 7

(Lemma 5 [23]). Let $D\in D{S}_n^{\prime }(d),$ where n is even, d is even and $d\ge 2.$ Let $x,y$ be any pair of vertices of D such that $x,y\in V(H).$ If $V(R)\cap V(L(D))=\varnothing ,$ then there exists a walk $W(x,y)$ from x to y such that $V(W(x,y))\cap V(L(D))\ne \varnothing ,$ and $|W(x,y)|\le n-d+1.$

Corollary 2.

Let $D\in D{S}_n^{\prime }(d),$ where n is even, d is even such that $d\ge 2.$ Let $x,y$ be any pair of vertices of D satisfying $x,y\in V(H).$ If $V(R)\cap V(L(D))=\varnothing ,$ then ${\gamma }_D(x,y)\le n-d+1.$

Proof. 

According to Lemma 7, there is a walk $W(x,y)$ from x to y passing through a loop vertex, and $|W(x,y)|\le n-d+1.$ Furthermore, according to Lemma 3, we have ${\gamma }_D(x,y)\le \left|W(x,y)\right|\le n-d+1.$ □

Theorem 3.

Let $D\in D{S}_n(d).$ If n is even, d is even and $d\ge 2,$ then

(1)

If $n\le 2d-2,$ then $ex{p}_D(k)\le \frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

(2)

If $n\ge 2d,$ then

$$ex{p}_D(k)\le \left\{\begin{array}{cc}n-d+1,\hfill & \mathit{where}1\le k\le n-2d+4,\hfill \\ n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,\hfill & \mathit{where}n-2d+4\le k\le n.\hfill \end{array}\right.$$

Proof. 

We only need to consider $D\in D{S}_n^{\prime }(d).$ Let x be any vertex. Let us consider the following two cases.

Case 1 $D\in D{S}_{n,1}^{\prime }(d).$

Since $v_f\in V_1$ and $v_g\in V_1,$ then $v_{n+1-f}\in V_2$ and $v_{n+1-g}\in V_2.$

Case 1.1 $V(R)\cap V(L(D))\ne \varnothing .$

Suppose $\{v_m,v_{n+1-m}\}\subseteq V(R)\cap V(L(D)).$ Then, $v_m$ and $v_{n+1-m}$ are loop vertices. According to Lemma 6, we have $d(x,v_m)\le \frac{n}{2}.$ Further, ${\gamma }_D(v_m)={\gamma }_D(v_{n+1-m})\le \frac{n}{2}.$ Then, $ex{p}_D(1)=ex{p}_D(2)\le {\gamma }_D(v_m)\le \frac{n}{2}.$ Therefore, according to Proposition 1 and Lemma 1, we have $ex{p}_D(k)\le \frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

(1)

If $n\le 2d-2,$ then the conclusion is clearly established.

(2)

If $n\ge 2d,$ for $1\le k\le n-2d+4,$ then $ex{p}_D(k)\le \frac{n}{2}-1+⌈\frac{k}{2}⌉\le \frac{n}{2}-1+\frac{n}{2}-d+2=n-d+1.$ For $n-2d+4\le k\le n,$ we have $ex{p}_D(k)\le \frac{n}{2}-1+⌈\frac{k}{2}⌉=\frac{n}{2}-1+⌈\frac{k-(n-2d+4)}{2}⌉+\frac{n}{2}-d+2=n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉.$

Case 1.2 $V(R)\cap V(L(D))=\varnothing .$

Then, $v_f\in V(H)\cap V(R),v_{n+1-f}\in V(H)\cap V(R).$

For $x\in V(H),$ according to Corollary 2, we have ${\gamma }_D(v_f,x)\le n-d+1.$

For any vertex $x\in V_1\backslash V(H),$ then $V(P_{D_1}(v_f,x))\cap V(L(D))\ne \varnothing .$ We have ${\gamma }_D(v_f,x)\le d_{D_1}(v_f,x)\le \frac{n}{2}.$

For any vertex $x\in V_2\backslash V(H),$ then $V(P_{D_2}(v_{n+1-f},x))\cap V(L(D))\ne \varnothing .$ Let the walk $W_D(v_f,x)$ be $v_f\stackrel{d_D(v_f,v_{n+1-g})}{\to }{v}_{n+1-g}\stackrel{d_{D_2}(v_{n+1-g},x)}{\to }x.$ Since $V(R)\cap V(L(D))=\varnothing ,$ then $V(P_{D_2}(v_{n+1-f},v_{n+1-g}))\cap V(L(D))=\varnothing .$ In addition, $V(P_{D_2}(v_{n+1-f},x))\cap V(L(D))\ne \varnothing .$ We have $V(P_{D_2}(v_{n+1-g},x))\cap V(L(D))\ne \varnothing .$ So $V(W_D(v_f,x))\cap V(L(D))\ne \varnothing .$ Moreover, $|W_D(v_f,x)|=1+d_{D_2}(v_{n+1-g},x)\le \frac{n}{2}.$ We have ${\gamma }_D(v_f,x)\le \left|W_D(v_f,x)\right|\le \frac{n}{2}.$

Therefore, we have ${\gamma }_D(v_f)={\gamma }_D(v_{n+1-f})\le max\{\frac{n}{2},n-d+1\}.$

(1)

If $n\le 2d-2,$ then $n-d+1\le \frac{n}{2}.$ Then, we have $ex{p}_D(1)=ex{p}_D(2)\le {\gamma }_D(v_f)\le \frac{n}{2}.$ Therefore, according to Proposition 1 and Lemma 1, $ex{p}_D(k)\le \frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

(2)

If $n\ge 2d,$ then $n-d+1\ge \frac{n}{2}+1.$ We have $ex{p}_D(1)=ex{p}_D(2)\le {\gamma }_D(v_f)\le n-d+1.$ Next, we construct a set $V(L_1)$ such that $|V(L_1)|\ge n-2d+4,$ and for any vertex $v_i\in V(L_1),$${\gamma }_D(v_i)\le n-d+1$ holds. Let $V(L_{11})=\{v:d_{D_1}(v,v_f)\le \frac{n-2d+2}{2},\mathit{where}v\in V_1\}.$ Let $V(L_{12})=\{v:d_{D_2}(v,v_{n+1-f})\le \frac{n-2d+2}{2},\mathit{where}v\in V_2\}.$ Suppose $V(L_1)=V(L_{11})\cup V(L_{12}).$ Then, $v_f\in V(L_1)$ and $v_{n+1-f}\in V(L_1).$ Suppose $v_h\in V(L_{11})$ and $v_h\ne v_f.$ If the vertex sequence of the unique path in $D_1$ from $v_h$ to $v_f$ is $v_h,\cdots ,v_t,\cdots ,v_f,$ then the vertex sequence of the unique path in $D_2$ from $v_{n+1-h}$ to $v_{n+1-f}$ is $v_{n+1-h},\cdots ,v_{n+1-t},\cdots ,v_{n+1-f}.$ So, $d_{D_1}(v_h,v_f)=d_{D_2}(v_{n+1-h},v_{n+1-f})\le \frac{n-2d+2}{2}.$ Therefore, we have $v_{n+1-h}\in V(L_1).$ Next, we prove that $|V(L_1)|\ge n-2d+4.$ For any vertex $v_s\in V(D),$ if $v_s\in V(L_1),$ then $|V(L_1)|=n.$ If there is a vertex $v_l$ satisfying $v_l\in V(D)\backslash V(L_1)$, we might as well assume $v_l\in V_1.$ Then $d_{D_1}(v_l,v_f)\ge \frac{n-2d+2}{2}+1.$ So, $V(P_{D_1}(v_l,v_f))\cap V(L_{11})=\frac{n-2d+2}{2}+1.$ Moreover, $V(P_{D_2}(v_{n+1-l},v_{n+1-f}))\cap V(L_{12})=\frac{n-2d+2}{2}+1.$ Then, $|\left(V(P_{D_1}(v_l,v_f))\cup V(P_{D_2}(v_{n+1-l},v_{n+1-f}))\right)\cap V(L_1)|=n-2d+4.$ Therefore, we have $|V(L_1)|\ge n-2d+4.$ Let us assume $v_i\in V(L_{11}).$ Next, we consider ${\gamma }_D(v_i).$

Case 1.2.1 $x\in V_1.$

Let $W_{D_1}(v_i,x)$ be the walk from $v_i$ to $x,$ which is $v_i\stackrel{d_{D_1}(v_i,v_f)}{\to }{v}_f\stackrel{d_{D_1}(v_f,x)}{\to }x.$ If the walk $W_{D_1}(v_i,x)$ passes through a loop vertex, we have $|W_{D_1}(v_i,x)|=d_{D_1}(v_i,v_f)+d_{D_1}(v_f,x)\le \frac{n-2d+2}{2}+\frac{n}{2}=n-d+1.$ If the walk $W_{D_1}(v_i,x)$ does not pass through a loop vertex, we have $x\in V(H)$ and $v_i\in V(H).$ According to Corollary 2, then ${\gamma }_D(v_i,x)\le n-d+1.$

Case 1.2.2 $x\in V_2.$

Let the walk $W_D(v_i,x)$ be $v_i\stackrel{d_{D_1}(v_i,v_f)}{\to }{v}_f\stackrel{d_D(v_f,v_{n+1-g})}{\to }{v}_{n+1-g}\stackrel{d_{D_2}(v_{n+1-g},x)}{\to }x.$ If the walk $W_D(v_i,x)$ passes through a loop vertex, we have $|W_D(v_i,x)|=d_{D_1}(v_i,v_f)+1+d_{D_2}(v_{n+1-g},x)\le \frac{n-2d+2}{2}+\frac{n}{2}=n-d+1.$ If the walk $W_D(v_i,x)$ does not pass through a loop vertex. Then, $v_i\in V(H).$ Since $V(R)\cap V(L(D))=\varnothing ,$ then $V(P_{D_2}(v_{n+1-f},v_{n+1-g}))\cap V(L(D))=\varnothing .$ Moreover, $V(P_{D_2}(v_{n+1-g},x))\cap V(L(D))=\varnothing ,$ we have $V(P_{D_2}(v_{n+1-f},x))\cap V(L(D))=\varnothing .$ So, we have $x\in V(H).$ Since $x\in V(H)$ and $v_i\in V(H),$ according to Corollary 2, then ${\gamma }_D(v_i,x)\le n-d+1.$

Therefore, whether $x\in V_1$ or $x\in V_2,$ we have ${\gamma }_D(v_i,x)\le n-d+1.$ So ${\gamma }_D(v_i)\le n-d+1.$ According to Proposition 1, we have ${\gamma }_D(v_{n+1-i})={\gamma }_D(v_i)\le n-d+1.$ Therefore, we have $ex{p}_D(k)\le n-d+1,$ where $1\le k\le |V(L_1)|.$ For any vertex $v_j$ such that $v_j\in V_1\backslash V(L_{11})$, then $v_{n+1-j}\in V_2\backslash V(L_{12}).$ We have $d_{D_1}(v_j,V(L_{11}))=d_{D_2}(v_{n+1-j},V(L_{12})).$ Furthermore, according to Lemma 2, we can conclude that ${\gamma }_D(v_j)={\gamma }_D(v_{n+1-j})\le n-d+1+d_{D_1}(v_j,V(L_{11})).$ Since $|V(L_1)|\ge n-2d+4,$ the conclusion is clearly established.

Case 2 $D\in D{S}_{n,2}^{\prime }(d).$

For $D\in D{S}_{n,2}^{\prime }(d),$ it is equivalent to $f=g$ in $D\in D{S}_{n,1}^{\prime }(d)$, let us omit it. □

3. The $\mathit{k}$th Local Exponents of ${\mathit{H}}^{*}$ and ${\mathit{H}}^{**}$

In this section, we study the kth local exponents of the special graphs $H^{*}$ and $H^{**}$.

Definition 4.

Suppose $1\le d\le n.$ Let $V(H^{*})=\{v_1,v_2,\cdots ,v_n\}$ and $E(H^{*})=\left\{[v_i,v_{i+1}]\right|1\le i\le n-1\}$$\cup E(L(H^{*})),$ where $E(L(H^{*}))$ are d loops arranged arbitrarily such that $H^{*}\in D{S}_n^{\prime }(d).$

Definition 5.

Suppose d is even and $d\ge 2$. Let $V(H^{**})=\{v_1,v_2,\cdots ,v_n\}$ and let $E(H^{**})=\left\{[v_i,v_{i+1}]\right|1\le i\le n-1\}\cup \{[v_i,v_i]:\mathit{where}1\le i\le \frac{d}{2}\mathrm{and}n-\frac{d}{2}+1\le i\le n\}.$

From the definition of $H^{*}$ and $H^{**},$ we know that $H^{*}\in D{S}_n^{\prime }(d)$ and $H^{**}\in D{S}_n^{\prime }(d).$ Furthermore, there is a unique path for any two different vertices in $H^{*}$ and $H^{**},$ respectively.

Remark 4.

In Figure 2, n can be either odd or even. In Figure 3, since n is odd and $n\ge 2d-1,$ then $v_{\frac{n+1}{2}}$ is not a loop vertex. In Figure 4, since n is even and $n\ge 2d,$ then $v_{\frac{n}{2}}$ and $v_{\frac{n}{2}+1}$ are not loop vertices.

Theorem 4.

If n is odd and d is odd, then $ex{p}_{H^{*}}(k)=\frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

Proof. 

Since d is odd, then $v_{\frac{n+1}{2}}$ is a loop vertex. We have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}})=max\{d(v_{\frac{n+1}{2}},x):x\in V(H^{*})\}=d(v_{\frac{n+1}{2}},v_n)=\frac{n-1}{2}.$ Moreover, according to Lemma 2, we have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a})\le {\gamma }_{H^{*}}(v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}-a},v_{\frac{n+1}{2}})=\frac{n-1}{2}+a,$ where $1\le a\le \frac{n-1}{2}.$ Further, ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a})={\gamma }_{H^{*}}(v_{\frac{n+1}{2}+a})={\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a},v_n)=d(v_{\frac{n+1}{2}-a},v_n)=\frac{n-1}{2}+a,$ where $1\le a\le \frac{n-1}{2}.$ Therefore, the theorem now holds. □

Theorem 5.

If n is odd, d is even and $d\ge 2,$ then

(1)

If $n\le 2d-3,$ then $ex{p}_{H^{*}}(k)=\frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

(2)

$n\ge 2d-1,$ then

$$ex{p}_{H^{**}}(k)=\left\{\begin{array}{cc}n-d+1,\hfill & \mathit{where}1\le k\le n-2d+4,\hfill \\ n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,\hfill & \mathit{where}n-2d+4\le k\le n.\hfill \end{array}\right.$$

Proof. 

Since d is even, then $v_{\frac{n+1}{2}}$ is not a loop vertex.

(1)

$H^{*}$ is shown in Figure 2. Let x be any vertex of $H^{*}$. If $V(P(v_{\frac{n+1}{2}},x))\cap V(L(H^{*}))\ne \varnothing ,$ then ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}},x)=d(v_{\frac{n+1}{2}},x)\le \frac{n-1}{2}.$ If $V(P(v_{\frac{n+1}{2}},x))\cap V(L(H^{*}))=\varnothing ,$ according to Corollary 1, we have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}},x)\le n-d+1.$ Then, ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}})\le max\{\frac{n-1}{2},n-d+1\}.$ If $n\le 2d-3,$ then $n-d+1\le \frac{n-1}{2}.$ Then, we have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Further, ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}},v_n)=d(v_{\frac{n+1}{2}},v_n)=\frac{n-1}{2}.$ Therefore, ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}})=\frac{n-1}{2}.$ Let a be an integer satisfying $1\le a\le \frac{n-1}{2}.$ According to Lemma 2, we have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a})\le d(v_{\frac{n+1}{2}-a},v_{\frac{n+1}{2}})+{\gamma }_{H^{*}}(v_{\frac{n+1}{2}})=a+\frac{n-1}{2}.$ Further, we have ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a},v_n)=d(v_{\frac{n+1}{2}-a},$

$v_n)=\frac{n-1}{2}+a.$ Then, ${\gamma }_{H^{*}}(v_{\frac{n+1}{2}-a})={\gamma }_{H^{*}}(v_{\frac{n+1}{2}+a})=\frac{n-1}{2}+a$ by Proposition 1, where $1\le a\le \frac{n-1}{2}.$ Therefore, we have $ex{p}_{H^{*}}(k)=\frac{n-1}{2}+⌊\frac{k}{2}⌋,$ where $1\le k\le n.$

(2)

$H^{**}$ is shown in Figure 3. If $n\ge 2d-1,$ then $n-d+1\ge \frac{n+1}{2}.$ Since $n\ge 5$ and $n\ge 2d-1,$ then $\frac{d}{2}\le \frac{n+1}{4}\le \frac{n-1}{2}$ and $n-\frac{d}{2}+1\ge n-\frac{n+1}{4}+1\ge \frac{n+3}{2}.$ Then, $v_{\frac{n+1}{2}}$ is not a loop vertex.

Suppose any integer a satisfies $d-1\le a\le \frac{n+1}{2}.$ Since $d\ge 2,$ then $a\ge d-1\ge \frac{d}{2}.$ Let x be any vertex of $H^{**}$. Let the walk $W(v_a,x)$ be $v_a\stackrel{d(v_a,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}\stackrel{d(v_{\frac{n+1}{2}},x)}{\to }x.$ If $V(W(v_a,x))\cap V(L(H^{**}))\ne \varnothing ,$ then ${\gamma }_{H^{**}}(v_a,x)\le (\frac{n+1}{2}-a)+\frac{n-1}{2}=n-a.$ If $V(W(v_a,x))\cap V(L(H^{**}))=\varnothing ,$ we have $V(P(x,v_{\frac{n+1}{2}}))\cap V(L(D))=\varnothing$ and $V(P(v_a,v_{\frac{n+1}{2}}))$

$\cap V(L(D))=\varnothing .$ According to Corollary 1, we have ${\gamma }_{H^{**}}(v_a,x)\le n-d+1.$ Therefore, we have ${\gamma }_{H^{**}}(v_a)\le max\{n-a,n-d+1\}=n-d+1,$ where $d-1\le a\le \frac{n+1}{2}.$ Since $d\ge 2$ and $d-1\le a\le \frac{n+1}{2},$ then $\frac{n+1}{2}\le n-a+1\le n-d+2\le n-\frac{d}{2}+1.$ Further, ${\gamma }_{H^{**}}(v_a,v_{n-a+1})=d(v_a,v_{\frac{d}{2}})+d(v_{\frac{d}{2}},v_{n-a+1})=d(v_a,v_{n-\frac{d}{2}+1})+d(v_{n-\frac{d}{2}+1},v_{n-a+1})=n-d+1.$ Therefore, ${\gamma }_{H^{**}}(v_a)=n-d+1,$ where $d-1\le a\le \frac{n+1}{2}.$ According to Proposition 1, if $\frac{n+1}{2}\le a\le n-d+2,$ we have ${\gamma }_{H^{**}}(v_a)={\gamma }_{H^{**}}(v_{n-a+1})=n-d+1.$ So, for $d-1\le a\le n-d+2,$ we have ${\gamma }_{H^{**}}(v_a)=n-d+1.$ Therefore, we have $ex{p}_{H^{**}}(k)=n-d+1,$ where $1\le k\le n-2d+4.$

Suppose a satisfies $1\le a\le d-1.$ We have ${\gamma }_{H^{**}}(v_a)\le d(v_a,v_{d-1})+{\gamma }_{H^{**}}(v_{d-1})=n-d+1+(d-1-a)=n-a.$ Moreover, ${\gamma }_{H^{**}}(v_a)={\gamma }_{H^{**}}(v_{n-a+1})=d(v_a,v_n)=n-a.$ So, we can get $ex{p}_{H^{**}}(k)=n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,$ where $n-2d+4\le k\le n.$

Therefore, the theorem now holds. □

Theorem 6.

If n is even, d is even and $d\ge 2,$ then

(1)

If $n\le 2d-2,$ then $ex{p}_{H^{*}}(k)=\frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

(2)

$n\ge 2d,$ then

$$ex{p}_{H^{**}}(k)=\left\{\begin{array}{cc}n-d+1,\hfill & \mathit{where}1\le k\le n-2d+4,\hfill \\ n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,\hfill & \mathit{where}n-2d+4\le k\le n.\hfill \end{array}\right.$$

Proof. 

(1)$H^{*}$ is shown in Figure 2. We have $H^{*}\in D{S}_{n,2}^{\prime }(d),$$f=g=\frac{n}{2}$ or $f=g=\frac{n}{2}+1.$ Let us assume $f=g=\frac{n}{2},$ then $n+1-f=n+1-g=\frac{n}{2}+1.$ If $n\le 2d-2,$ let us consider the following two cases.

Case 1 $\{v_{\frac{n}{2}},v_{\frac{n}{2}+1}\}\cap V(L(H^{*}))\ne \varnothing .$

It is easy to see that ${\gamma }_{H^{*}}(v_{\frac{n}{2}})={\gamma }_{H^{*}}(v_{\frac{n}{2}+1})=max\{d(v_{\frac{n}{2}},x):x\in V(H^{*})\}=d(v_{\frac{n}{2}},v_n)=\frac{n}{2}.$ Suppose a satisfies $1\le a\le \frac{n}{2}-1.$ According to Lemma 2, we can get ${\gamma }_{H^{*}}(v_{\frac{n}{2}-a})\le d(v_{\frac{n}{2}-a},v_{\frac{n}{2}})+{\gamma }_{H^{*}}(v_{\frac{n}{2}})=\frac{n}{2}+a.$ Further, ${\gamma }_{H^{*}}(v_{\frac{n}{2}-a})={\gamma }_{H^{*}}(v_{\frac{n}{2}-a},v_n)=d(v_{\frac{n}{2}-a},v_n)=\frac{n}{2}+a.$ According to Proposition 1, we have ${\gamma }_{H^{*}}(v_{\frac{n}{2}-a})={\gamma }_{H^{*}}(v_{\frac{n}{2}+a+1})=\frac{n}{2}+a,$ where $1\le a\le \frac{n}{2}-1.$ Therefore, we have $ex{p}_{H^{*}}(k)=\frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

Case 2 $\{v_{\frac{n}{2}},v_{\frac{n}{2}+1}\}\cap V(L(H^{*}))=\varnothing .$

Let x be any vertex of $H^{*}.$ If $V(P(v_{\frac{n}{2}},x))\cap V(L(H^{*}))\ne \varnothing ,$ then ${\gamma }_{H^{*}}(v_{\frac{n}{2}},x)=d(v_{\frac{n}{2}},x)\le \frac{n}{2}.$ If $V(P(v_{\frac{n}{2}},x))\cap V(L(H^{*}))=\varnothing ,$ according to Corollary 2, we have ${\gamma }_{H^{*}}(v_{\frac{n}{2}},x)$

$\le n-d+1.$ Then, ${\gamma }_{H^{*}}(v_{\frac{n}{2}})\le max\{\frac{n}{2},n-d+1\}=\frac{n}{2}.$ Further, we have ${\gamma }_{H^{*}}(v_{\frac{n}{2}})={\gamma }_{H^{*}}(v_{\frac{n}{2}},v_n)=d(v_{\frac{n}{2}},v_n)=\frac{n}{2}.$ Let a satisfy that $1\le a\le \frac{n}{2}-1.$ Then, ${\gamma }_{H^{*}}(v_{\frac{n}{2}-a})\le d(v_{\frac{n}{2}-a},v_{\frac{n}{2}})+{\gamma }_{H^{*}}(v_{\frac{n}{2}})=\frac{n}{2}+a.$ Further, we have ${\gamma }_{H^{*}}(v_{\frac{n}{2}-a})={\gamma }_{H^{*}}(v_{\frac{n}{2}-a},v_n)=d(v_{\frac{n}{2}-a},v_n)$

$=\frac{n}{2}+a.$ According to Proposition 1, ${\gamma }_{H^{*}}(v_{\frac{n}{2}+1+a})={\gamma }_{H^{*}}(v_{\frac{n}{2}-a})=\frac{n}{2}+a,$ where $0\le a\le \frac{n}{2}-1.$ Therefore, we have $ex{p}_{H^{*}}(k)=\frac{n}{2}-1+⌈\frac{k}{2}⌉,$ where $1\le k\le n.$

(2) $H^{**}$ is shown in Figure 4. We have $H^{**}\in D{S}_{n,2}^{\prime }(d),$$f=g=\frac{n}{2}$ or $f=g=\frac{n}{2}+1.$ Let us assume $f=g=\frac{n}{2},$ then $n+1-f=n+1-g=\frac{n}{2}+1.$ If $n\ge 2d,$ then $n-d+1\ge \frac{n}{2}+1.$ Since $n\ge 6$ and $n\ge 2d,$ then $\frac{d}{2}\le \frac{n}{4}\le \frac{n}{2}-1$ and $n-\frac{d}{2}+1\ge n-\frac{n}{4}+1\ge \frac{n}{2}+2.$ Then $v_{\frac{n}{2}}$ and $v_{\frac{n}{2}+1}$ are not loop vertices.

Suppose any integer a satisfies $d-1\le a\le \frac{n}{2}.$ Since $d\ge 2,$ then $a\ge d-1\ge \frac{d}{2}.$ Let x be any vertex of $H^{**}.$ Let the walk $W(v_a,x)$ be $v_a\stackrel{d(v_a,v_{\frac{n}{2}})}{\to }{v}_{\frac{n}{2}}\stackrel{d(v_{\frac{n}{2}},x)}{\to }x.$ If $V(W(v_a,x))\cap V(L(H^{**}))\ne \varnothing ,$ then ${\gamma }_{H^{**}}(v_a,x)\le (\frac{n}{2}-a)+\frac{n}{2}=n-a.$ If $V(W(v_a,x))\cap V(L(H^{**}))=\varnothing ,$ we have $V(P(v_a,v_{\frac{n}{2}}))\cap V(L(D))=\varnothing$ and $V(P(x,v_{\frac{n}{2}}))\cap V(L(D))=\varnothing .$ According to Corollary 2, we have ${\gamma }_{H^{**}}(v_a,x)\le n-d+1.$ So ${\gamma }_{H^{**}}(v_a)\le max\{n-a,n-d+1\}=n-d+1,$ where $d-1\le a\le \frac{n}{2}.$ Since $d\ge 2$ and $d-1\le a\le \frac{n}{2},$ then $\frac{n}{2}+1\le n-a+1\le n-d+2\le n-\frac{d}{2}+1.$ Further, we have ${\gamma }_{H^{**}}(v_a)={\gamma }_{H^{**}}(v_a,v_{n-a+1})=d(v_a,v_{\frac{d}{2}})+d(v_{\frac{d}{2}},v_{n-a+1})=d(v_a,v_{n-\frac{d}{2}+1})+d(v_{n-\frac{d}{2}+1},v_{n-a+1})=n-d+1,$ where $d-1\le a\le \frac{n}{2}.$ According to Proposition 1, if $\frac{n}{2}+1\le a\le n-d+2,$ we have ${\gamma }_{H^{**}}(v_a)={\gamma }_{H^{**}}(v_{n-a+1})=n-d+1.$ So, for $d-1\le a\le n-d+2,$ we have ${\gamma }_{H^{**}}(v_a)=n-d+1.$ Therefore, we have $ex{p}_{H^{**}}(k)=n-d+1,$ where $1\le k\le n-2d+4.$

Suppose a satisfies $1\le a\le d-1.$ We have ${\gamma }_{H^{**}}(v_a)\le d(v_a,v_{d-1})+{\gamma }_{H^{**}}(v_{d-1})=n-d+1+(d-1-a)=n-a.$ Moreover, ${\gamma }_{H^{**}}(v_a)={\gamma }_{H^{**}}(v_{n-a+1})=d(v_a,v_n)=n-a.$ So, we can get $ex{p}_{H^{**}}(k)=n-d+1+⌈\frac{k-(n-2d+4)}{2}⌉,$ where $n-2d+4\le k\le n.$

Therefore, the theorem now holds. □

It can be seen from Theorems 4–6, the upper bound for the kth local exponent of doubly symmetric primitive digraphs of order n with d loops can be reached, where $1\le k\le n$.

4. Conclusions

In this paper, we study the upper bound for the kth local exponent of doubly symmetric primitive digraphs of order n with d loops, where d is an integer such that $1\le d\le n.$ For the class of doubly symmetric primitive digraphs, we get the upper bound for the kth local exponent, where $1\le k\le n.$ Furthermore, for the class of doubly symmetric primitive digraphs, we find that the upper bound for the kth local exponent can be reached, where $1\le k\le n.$ The upper bounds of the generalized $\mu$-scrambling indices for a doubly symmetric primitive digraph are not given. It would be meaningful and interesting to solve the problems in future research.