The Generalized Competition Indices of Doubly Symmetric Primitive Digraphs with d Loops

Abstract

Let $D{S}_n\left(d\right)$ denote the set of all doubly symmetric primitive digraphs of order n with d loops, where d is an integer and $1\le d\le n.$ In this paper, we determine the upper bounds for the m-competition indices(generalized competition indices) of $D{S}_n\left(d\right)$, where $1\le m\le n.$ If n and d satisfy that n is odd and d is odd, or $n\le 2d-2$ and d is even such that $d\ge 2,$ then the upper bounds for the m-competition indices of $D{S}_n\left(d\right)$ can be reached, where $1\le m\le n.$

1. Introduction

In this paper, the terminology and notation used follow from [1,2,3,4], and all digraphs (directed graphs) do not involve weights. Let $D=(V,E)$ denote a digraph (directed graph) with vertex set $V=V\left(D\right),$ arc set $E=E\left(D\right)$ and order $n.$ Loops are permitted, but multiple arcs are not. A walk W from x to y in a digraph $D,$ referring to a sequence of vertices $x,v_1,\cdots ,v_{k-1},y\in V\left(D\right),$ and a sequence of arcs $(x,v_1),(v_1,v_2),\cdots ,(v_{k-1},y)\in E\left(D\right),$ where the vertices and arcs are not necessarily distinct. The length of the walk W refers to the number of arcs in $W.$ The walk W from x to y of length k is denoted as $x\stackrel{k}{\to }y.$ A path is a walk with distinct vertices. A cycle is a closed walk from x to y with distinct vertices except for $x=y.$ The length of the shortest walk from x to y is called the distance from vertex x to vertex $y,$ and it is denoted by $d_D(x,y)$ (for short, $d(x,y)$).

A digraph D is called primitive if and only if there exists some positive integer k such that for any pair of vertices $x,y$ of $D,$ there is a walk of length k from x to $y.$ The smallest such k is called the exponent of $D,$ denoted by $exp\left(D\right).$ It is well known that D is primitive if and only if D is strongly connected, and the greatest common divisor of the lengths of all the cycles in D is 1.

For a positive integer m that satisfies $1\le m\le n,$ and D is a primitive digraph, we define the m-competition index (generalized competition index) of $D,$ it is denoted by $k_m\left(D\right),$ which is the smallest positive integer k such that for any pair of vertices $x,y,$ there exist at least m distinct vertices $v_1,v_2,\cdots ,v_m$ of D that satisfy $x\stackrel{k}{\to }{v}_i$ and $y\stackrel{k}{\to }{v}_i,$ where $1\le i\le m.$

The scrambling index of a primitive digraph D was introduced in [4,5], and denoted by $k\left(D\right).$ Kim [6] studied the scrambling index of primitive digraphs. Chen and Liu [7] studied the scrambling index of symmetric primitive matrices (digraphs). Kim [8] introduced the m-competition index, which is a generalization of the competition index in [3]. For primitive digraphs, the definitions of 1-competition index and the scrambling index are identical. That is, $k\left(D\right)=k_1\left(D\right).$

For a positive integer k and a primitive digraph $D,$ we define the k-step outneighborhood of a vertex x as

$$N^{+}(D^k:x)=\{v\in V\left(D\right)|x\stackrel{k}{\to }v\}.$$

The k-step common outneighborhood of vertices x and y is defined as

$$N^{+}(D^k:x,y)=N^{+}(D^k:x)\cap N^{+}(D^k:y).$$

The local m-competition index of vertices x and y as

$$k_m(D:x,y)=min\{k:|N^{+}(D^t:x,y)|\ge m,\mathrm{and}t\ge k\}$$

The local m-competition index of x as

$$k_m(D:x)=\underset{y\in V\left(D\right)}{max}\left\{k_m(D:x,y)\right\}.$$

Then, we have

$$k_m\left(D\right)=\underset{x\in V\left(D\right)}{max}{k}_m(D:x)=\underset{x,y\in V\left(D\right)}{max}{k}_m(D:x,y).$$

According to the definitions of $k_m\left(D\right),$ $k_m(D:x)$ and $k_m(D:x,y),$ we can easily get $k_m(D:x,y)\le k_m(D:x)\le k_m\left(D\right).$ On the basis of the definitions of the exponent and the m-competition index of D of order $n,$ we have

$$k\left(D\right)=k_1\left(D\right)\le k_2\left(D\right)\le \cdots \le k_n\left(D\right)=exp\left(D\right).$$

The m-competition index is a generalization of the exponent and the scrambling index of a primitive digraph. There exist many studies about exponents and their generalization; for example [9,10,11]. For some studies on generalized competition indices, see [12,13,14,15,16].

Remark 1.

Brualdi and Liu [10] proposed a memoryless communication system. In a memoryless communication system represented by a primitive digraph with n vertices, Huang and Liu [17] pointed out the m-competition indices characterize the longest first time of m vertices knowing all 2 bits of the information. See [10,17] for more details.

For a primitive digraph, Huang and Liu [17] gave the definition of the generalized $\mu$-scrambling indices, which are a generalization of the scrambling index and m-competition index. For the research on the generalized $\mu$-scrambling indices, please refer to [18,19]. Topological indices of graphs were studied in [20,21,22,23]. Furthermore, graphs have some applications in chemistry. For chemical graphs, we refer to [24,25].

A symmetric digraph D is a digraph such that for any vertices x and $y,$ $(x,y)\in E\left(D\right)$ is an arc if and only if $(y,x)\in E\left(D\right)$ is an arc, which is represented by $x\leftrightarrow y.$ An undirected graph (possibly with loops) can be regarded as a symmetric digraph. If D is symmetric, the notation $x\stackrel{k}{\to }y$ is used to represent that there exists a walk of length k from x to $y.$

A doubly symmetric digraph $D=(V,E),$ where $V=\{v_1,v_2,\cdots ,v_n\}.$ A doubly symmetric digraph D is a symmetric digraph such that for any pair of vertices $v_i$ and $v_j,$ $(v_i,v_j)\in E\left(D\right)$ is an arc if and only if $(v_{n+1-i},v_{n+1-j})\in E\left(D\right)$ is an arc. In addition, we call the two arcs $(v_i,v_j)$ and $(v_{n+1-i},v_{n+1-j})$ as a pair of symmetrical arcs, or $(v_{n+1-i},v_{n+1-j})$ as the symmetrical arc of $(v_i,v_j),$ where $1\le i\le n$ and $1\le j\le n.$ We call the two vertices $v_{n+1-i}$ and $v_i$ as a pair of symmetrical vertices, or $v_{n+1-i}$ as the symmetrical vertex of $v_i,$ where $1\le i\le n.$ By definition, if n is odd, then $v_{\frac{n+1}{2}}$ is symmetrical with itself. If $(v_i,v_i)\in E\left(D\right),$ then $(v_{n+1-i},v_{n+1-i})\in E\left(D\right).$ In other words, 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 digraph D is called a doubly symmetric primitive digraph provided D is a doubly symmetric digraph and D is primitive.

Chen and Liu [26,27] investigated exponents and their generalization about doubly symmetric primitive matrices(primitive digraphs). Chen and Jiang [28] studied exponent sets of central symmetric primitive matrices (doubly symmetric primitive digraphs) with trace d (d loops).

A doubly symmetric primitive digraph D is called as a doubly symmetric primitive digraph with d loops if and only if D contains exactly d loops. Let $D{S}_n$ denote the set of all doubly symmetric primitive digraphs with n vertices. Let $D{S}_n\left(d\right)$ denote the set of all doubly symmetric primitive digraphs of order n with d loops, where $1\le d\le n.$ Let $V\left(L\right(D\left)\right)$ represent the set of d loop vertices in $D,$ where $D\in D{S}_n\left(d\right).$ Let $D{S}_n^{\prime }\left(d\right)\subseteq D{S}_n\left(d\right).$ Let $D\in D{S}_n^{\prime }\left(d\right)$ and if we delete any pair of symmetric arcs $(v_i,v_j)$ and $(v_{n+1-i},v_{n+1-j})$ of $D,$ then D is not a doubly symmetric primitive digraph (that is, D is not connected), where $1\le i<j\le n.$

Kim and Lee [16] investigated m-competition indices of symmetric primitive digraphs with the shortest odd cycle length $s,$ and gave the upper and lower bounds, where $s\ge 1.$ A doubly symmetric primitive digraph is a special symmetric primitive digraph, which has the characteristic of arc symmetry. In this paper, according to the arc symmetry of such digraphs, using graph theory methods, we determine the upper bounds for the m-competition indices of $D{S}_n\left(d\right)$, where $1\le m\le n.$

If a walk from $v_i$ to $v_j$ in a digraph D is recorded as $W(v_i,v_j),$ then the length of the walk $W(v_i,v_j)$ is recorded as $\left|W\right(v_i,v_j\left)\right|,$ the set of all vertices on this walk is denoted as $V\left(W(v_i,v_j)\right).$ If there is a unique path from $v_i$ to $v_j$ in a digraph $D,$ then the path is recorded as $P_D(v_i,v_j)$ (for short, $P(v_i,v_j)$). The length of the path $P_D(v_i,v_j)$ is written as $|P_D(v_i,v_j)|$ (for short, $\left|P\right(v_i,v_j\left)\right|$). The set of all vertices on the path is denoted as $V\left(P_D(v_i,v_j)\right)$ (for short, $V\left(P(v_i,v_j)\right)$). If $v_i=v_j,$ we define $V\left(P(v_i,v_j)\right)=\left\{v_i\right\}.$ If $v_l$ is a vertex on the path $P(v_i,v_j)$ from $v_i$ to $v_j,$ then we call $v_l\in V\left(P(v_i,v_j)\right).$ For a vertex $x\in V\left(D\right)$ and a set $X\subseteq V\left(D\right),$ let $d(x,X)=min\{d(x,v_i):v_i\in X\}.$ For $x\in X,$ we define $d(x,X)=0.$ If U is a set, we use the sign $\left|U\right|$ to denote the number of elements in $U.$ The sign $⌊x⌋$ is used to represent the largest integer not greater than $x,$ and the sign $⌈y⌉$ is used to represent the smallest integer not less than $y.$

In this paper, let $n,d$ and m be integers with $n\ge 5,$ $1\le m\le n,1\le d\le n.$ We give the upper bounds on the m-competition indices of digraphs in $D{S}_n\left(d\right),$ where $1\le m\le n.$

2. Preliminary Results

In Lemmas 1 and 2, let $D\in D{S}_n$ and $D=(V,E),$ where $V=\{v_1,v_2,\cdots ,v_n\}.$

Definition 1.

Let $D\in D{S}_n.$ We define the notation $E\left(S\right)=\{(v_t,v_{n+1-t}):(v_t,v_{n+1-t})\in E\left(D\right),$ $\mathrm{where}1\le t\le n\}.$

Chen and Jiang [28] gave the proof of Lemma 1, which was proved by contradictory method.

Lemma 1

(Chen and Jiang [28]). Let n be odd, and let x be a vertex of D. Then, $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$

Proof. 

Through the following steps, we find a subgraph $D_1^{*}$ of $D.$

(i)

Let $T_0=S{T}_0=\left\{v_{\frac{n+1}{2}}\right\}.$ Let $E_0=\varnothing$ and $S{E}_0=\varnothing .$

(ii)

Let i be an integer satisfying $1\le i\le \frac{n-1}{2}.$ If $T_{i-1}$ is known, then let $U_i=\{(x,y):(x,y)\in E\left(D\right),\mathrm{where}x\notin T_{i-1}\cup S{T}_{i-1}\mathrm{and}y\in T_{i-1}\}.$ For any arc $(v_{j_i},v_{h_i})$ of $U_i,$ we have $(v_{n+1-j_i},v_{n+1-h_i})\in E\left(D\right),$ where $v_{h_i}\in T_{i-1}.$ Let $e_i=(v_{j_i},v_{h_i}),$ $s{e}_i=(v_{n+1-j_i},v_{n+1-h_i}).$ Let $E_i=\left\{e_i\right\}\cup E_{i-1},S{E}_i=\left\{s{e}_i\right\}\cup S{E}_{i-1}.$ Let $T_i=T_{i-1}\cup \left\{v_{j_i}\right\},$ $S{T}_i=S{T}_{i-1}\cup \left\{v_{n+1-j_i}\right\}.$

(iii)

Repeat (ii), that is, i takes integers $1,2,\cdots ,\frac{n-1}{2}$ in turn, until $|T_{\frac{n-1}{2}}|=\frac{n+1}{2}.$

Then, $|T_{\frac{n-1}{2}}|=|S{T}_{\frac{n-1}{2}}|=\frac{n+1}{2}$ and $|E_{\frac{n-1}{2}}|=|S{E}_{\frac{n-1}{2}}|=\frac{n-1}{2}.$ Suppose $V_{11}=T_{\frac{n-1}{2}},$ $E_{11}=E_{\frac{n-1}{2}},V_{12}=S{T}_{\frac{n-1}{2}},E_{12}=S{E}_{\frac{n-1}{2}}.$ We have $|V_{11}|=|V_{12}|=\frac{n+1}{2},|E_{11}|=|E_{12}|=\frac{n-1}{2}.$ Let $D_{11}=(V_{11},E_{11}),D_{12}=(V_{12},E_{12}).$ According to the structure of $D_{11},D_{12},$ we can conclude that the both $D_{11}$ and $D_{12}$ are connected, and there is a unique path for any two different vertices in $D_{11}$ and $D_{12},$ respectively. Suppose $V_1^{*}=V_{11}\cup V_{12},E_1^{*}=E_{11}\cup E_{12}.$ Then, we have $V_1^{*}=V.$ Let $D_1^{*}=(V_1^{*},E_1^{*})$ denote a digraph (directed graph) with vertex set $V_1^{*},$ arc set $E_1^{*},$ and $|V_1^{*}|=n,|E_1^{*}|=n-1.$ We can conclude that the $D_1^{*}$ is connected, and there is a unique path for any two different vertices in $D_1^{*}.$ According to the structure of $D_1^{*}$, we know that $D_1^{*}$ is some subgraph of $D.$ For any vertex x of $D_1^{*},$ it’s easy to know that $d_{D_1^{*}}(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Therefore, the conclusion is established. □

Remark 2.

In order to obtain more conclusions and facilitate the following proofs, we take a different approach from [28] above to prove Lemma 1.

Lemma 2.

Let n be even, and let x be any vertex of D.

(1) 

If $E\left(S\right)=\varnothing ,$ then there is a cycle $C,$ so that for any vertex $v_g$ on the cycle $C,$ we have $d(x,v_g)\le \frac{n}{2}.$

(2) 

If $E\left(S\right)\ne \varnothing ,$ then there are vertices $v_t,v_{n+1-t},$ we have $d(x,v_t)\le \frac{n}{2},$ and $d(x,v_{n+1-t})\le \frac{n}{2}.$

Proof. 

Through the following steps, we find a subgraph $D_2^{*}$ of $D.$

(i)

Take any vertex $v_l$ of $D,$ let $T_0=\left\{v_l\right\}$ and $S{T}_0=\left\{v_{n+1-l}\right\}.$ Let $E_0=\varnothing$ and $S{E}_0=\varnothing .$

(ii)

Let i be an integer satisfying $1\le i\le \frac{n}{2}-1.$ If $T_{i-1}$ is known, then let $U_i=\{(x,y):(x,y)\in E\left(D\right),\mathrm{where}x\notin T_{i-1}\cup S{T}_{i-1}\mathrm{and}y\in T_{i-1}\}.$ For any arc $(v_{j_i},v_{h_i})$ of $U_i,$ we have $(v_{n+1-j_i},v_{n+1-h_i})\in E\left(D\right),$ where $v_{h_i}\in T_{i-1}.$ Let $e_i=(v_{j_i},v_{h_i}),$ $s{e}_i=(v_{n+1-j_i},v_{n+1-h_i}).$ Let $E_i=\left\{e_i\right\}\cup E_{i-1},S{E}_i=\left\{s{e}_i\right\}\cup S{E}_{i-1}.$ Let $T_i=T_{i-1}\cup \left\{v_{j_i}\right\},$ $S{T}_i=S{T}_{i-1}\cup \left\{v_{n+1-j_i}\right\}.$

(iii)

Repeat (ii), that is, i takes integers $1,2,\cdots ,\frac{n}{2}-1$ in turn, until $|T_{\frac{n}{2}-1}|=\frac{n}{2}.$

Then, $|T_{\frac{n}{2}-1}|=|S{T}_{\frac{n}{2}-1}|=\frac{n}{2}$ and $|E_{\frac{n}{2}-1}|=|S{E}_{\frac{n}{2}-1}|=\frac{n}{2}-1.$ Suppose $V_{21}=T_{\frac{n}{2}-1},$ $E_{21}=E_{\frac{n}{2}-1},V_{22}=S{T}_{\frac{n}{2}-1},E_{22}=S{E}_{\frac{n}{2}-1}.$ We have $|V_{21}|=|V_{22}|=\frac{n}{2},|E_{21}|=|E_{22}|=\frac{n}{2}-1.$ Let $D_{21}=(V_{21},E_{21}),D_{22}=(V_{22},E_{22}).$ According to the structure of $D_{21},D_{22},$ we can conclude that the both $D_{21}$ and $D_{22}$ are connected, and there is a unique path for any two different vertices in $D_{21}$ and $D_{22}$, respectively.

Case 1 $E\left(S\right)=\varnothing .$

Because D is connected, then there are $(v_t,v_{n+1-f})\in E\left(D\right)$ and $(v_f,v_{n+1-t})\in E\left(D\right),$ where $t\ne f.$ Suppose $v_t\in V_{21}$ and $v_f\in V_{21},$ then $v_{n+1-t}\in V_{22}$ and $v_{n+1-f}\in V_{22}.$ Suppose $V_2^{*}=V_{21}\cup V_{22},$ $E_2^{*}=E_{21}\cup E_{22}\cup \left\{(v_t,v_{n+1-f})\right\}\cup \left\{(v_f,v_{n+1-t})\right\}.$ Let $D_2^{*}=(V_2^{*},E_2^{*})$ denote a digraph (directed graph) with vertex set $V_2^{*},$ arc set $E_2^{*},$ and $|V_2^{*}|=n,|E_2^{*}|=n.$ According to the structure of $D_2^{*}$, we know that $D_2^{*}$ is some subgraph of $D.$ Let x be any vertex of $D_2^{*}.$ If $x\in V_{21},$ then there is a path $P_{D_{21}}(x,v_t)$ from x to $v_t,$ that is $x\stackrel{d_{D_{21}}(x,v_t)}{\to }{v}_t.$ We have $d_{D_2^{*}}(x,v_t)\le \frac{n}{2}-1.$ If $x\in V_{22},$ then there is a path $P_{D_2^{*}}(x,v_t)$ from x to $v_t,$ that is $x\stackrel{d_{D_{22}}(x,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_{D_2^{*}}(v_{n+1-f},v_t)}{\to }{v}_t.$ Since $\left\{(v_{n+1-f},v_t)\right\}\subseteq E_2^{*},$ then $d_{D_2^{*}}(v_{n+1-f},v_t)=1.$ We have $d_{D_2^{*}}(x,v_t)\le \frac{n}{2}.$ Therefore, for any vertex x of $D_2^{*},$ we have $d_{D_2^{*}}(x,v_t)\le \frac{n}{2}.$ Similarly, $d_{D_2^{*}}(x,v_{n+1-t})\le \frac{n}{2}.$ Therefore, for any vertex x of $D,$ we have $d(x,v_t)\le \frac{n}{2}$ and $d(x,v_{n+1-t})\le \frac{n}{2}.$ Similarly, we have $d(x,v_f)\le \frac{n}{2}$ and $d(x,v_{n+1-f})\le \frac{n}{2}.$ Let a sequence of vertices in the cycle C be $v_t,\cdots ,v_g,\cdots ,v_f,v_{n+1-t},\cdots ,v_{n+1-g},\cdots ,v_{n+1-f},v_t.$ If the length of cycle C is greater than or equal to $6,$ we will prove that for any vertex $v_g,v_{n+1-g}\in V\left(C\right),$ we have $d(x,v_g)\le \frac{n}{2}$ and $d(x,v_{n+1-g})\le \frac{n}{2}.$ Next, we consider $D_2^{*}.$ Suppose $v_t,\cdots ,v_g,\cdots ,v_f\in V_{21},$ then $v_{n+1-t},\cdots ,v_{n+1-g},\cdots ,v_{n+1-f}\in V_{22}.$ If $x\in V_{22},$ $d_{D_2^{*}}(x,v_{n+1-g})\le \frac{n}{2}$ is obvious. If $x\in V_{21},$ let $d_{D_{21}}(x,V\left(P_{D_{21}}(v_t,v_f)\right))=d_{D_{21}}(x,v_l),$ then $v_l\in V\left(P_{D_{21}}(v_t,v_f)\right).$ There is a path $P_1(x,v_{n+1-g})$ from x to $v_{n+1-g},$ that is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_f)}{\to }{v}_f\stackrel{d_D(v_f,v_{n+1-t})}{\to }{v}_{n+1-t}\stackrel{d_{D_{22}}(v_{n+1-t},v_{n+1-g})}{\to }{v}_{n+1-g}.$ There is another path $P_2(x,v_{n+1-g})$ from x to $v_{n+1-g},$ that is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_t)}{\to }{v}_t\stackrel{d_D(v_t,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_{D_{22}}(v_{n+1-f},v_{n+1-g})}{\to }{v}_{n+1-g}.$ Let the symmetry vertex of x be $x^{\prime }.$ We have $d_{D_{21}}(x,v_l)=d_{D_{22}}(x^{\prime },v_{n+1-l}),$ where $x^{\prime }\in V_{22}$ and $v_{n+1-l}\in V\left(P_{D_{22}}(v_{n+1-t},v_{n+1-f})\right).$

It’s easy to conclude $|P_1(x,v_{n+1-g})|+|P_2(x,v_{n+1-g})|\le |V\left(D\right)|=n.$ Then, we have $min\left\{\right|P_1(x,v_{n+1-g})|,|P_2(x,v_{n+1-g})\left|\right\}\le \frac{n}{2}.$ Therefore, $d_{D_2^{*}}(x,v_{n+1-g})\le \frac{n}{2}.$ Similarly, we have $d_{D_2^{*}}(x,v_g)\le \frac{n}{2}.$

Case 2 $E\left(S\right)\ne \varnothing .$

Since $E\left(S\right)\ne \varnothing ,$ there is $(v_t,v_{n+1-t})$ such that $(v_t,v_{n+1-t})\in E\left(D\right),$ where $1\le t\le n.$ Suppose $V_2^{**}=T_{\frac{n}{2}-1}\cup S{T}_{\frac{n}{2}-1},$ $E_2^{**}=E_{\frac{n}{2}-1}\cup S{E}_{\frac{n}{2}-1}\cup \left\{(v_t,v_{n+1-t})\right\}.$ Let $D_2^{**}=(V_2^{**},E_2^{**})$ denote a digraph with vertex set $V_2^{**},$ arc set $E_2^{**},$ and $|V_2^{**}|=n,|E_2^{**}|=n-1.$ We can conclude that $D_2^{**}$ is connected, and there is a unique path for any two different vertices in $D_2^{**}.$ According to the structure of $D_2^{**},$ we know that $D_2^{**}$ is some subgraph of $D.$ For any vertex x of $D_2^{**},$ it is easy to know that $d_{D_2^{**}}(x,v_t)\le \frac{n}{2},d_{D_2^{**}}(x,v_{n+1-t})\le \frac{n}{2}.$

In fact, if $t=f,$ the structures of the two graphs $D_2^{**}$ and $D_2^{*}$ are the same, and Case 2 can be regarded as a special case of Case 1.

Therefore, the conclusion is established. □

3. The Upper Bounds for the $\mathit{m}$-Competition Indices of ${\mathit{DS}}_{\mathit{n}}\left(\mathit{d}\right)$

Theorem 1.

Let $D\in D{S}_n\left(d\right).$ If n is odd and d is odd, then $k_m\left(D\right)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$

Proof. 

If d is odd, then $v_{\frac{n+1}{2}}$ is a loop vertex. Let x be any vertex. According to Lemma 1, we have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Therefore, we conclude $k_1\left(D\right)\le \frac{n-1}{2}.$ Since $d(v_1,v_{\frac{n+1}{2}})=d(v_n,v_{\frac{n+1}{2}}),d(v_2,v_{\frac{n+1}{2}})=d(v_{n-1},v_{\frac{n+1}{2}}),\cdots ,d(v_{\frac{n-1}{2}},v_{\frac{n+1}{2}})=d(v_{\frac{n+3}{2}},v_{\frac{n+1}{2}}),$ we have $k_m\left(D\right)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$ □

For any $D_1\in D{S}_n\left(d\right),$ then there is a spanning subgraph $D_2$ of $D_1$ ($V\left(D_1\right)=V\left(D_2\right)$ and $E\left(D_2\right)\subseteq E\left(D_1\right)$), and $D_2\in D{S}_n\left(d\right).$ We have $k_m\left(D_1\right)\le k_m\left(D_2\right),$ where $1\le m\le n.$ Therefore, when we study the upper bound on the m-competition indices of $D{S}_n\left(d\right),$ we only need to consider $D\in D{S}_n^{\prime }\left(d\right).$

Definition 2.

Let $D\in D{S}_n^{\prime }\left(d\right).$ For a pair of vertices $x,z,$ if there is a walk $W(x,z)$ from x to z through a loop vertex, we call $V\left(W\right(x,z\left)\right)\cap V\left(L\right(D\left)\right)\ne \varnothing .$ The set of d loops in D is denoted by $E\left(L\right(D\left)\right),$ and the loops appear in pairs.

Corollary 1.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is odd and $1\le d\le n.$

(1) 

There are two connected subgraphs $D_{11}$ and $D_{12}$ of $D,$ we have $V\left(D\right)=V_{11}\cup V_{12}$ and $E\left(D\right)=E_{11}\cup E_{12}\cup E\left(L\left(D\right)\right).$ Where $D_{11}=(V_{11},E_{11})$ and $D_{12}=(V_{12},E_{12}),$ $V_{11}=\{v_{n+1-i}:v_i\in V_{12}\}$ and $E_{11}=\{(v_{n+1-i},v_{n+1-j}):(v_i,v_j)\in E_{12}\}.$ Moreover, $|V_{11}|=|V_{12}|=\frac{n+1}{2},|E_{11}|=|E_{12}|=\frac{n-1}{2}.$

(2) 

For any pair of vertices $x,y$ of D such that $x\in V_{11}$ and $y\in V_{12},$ then $V\left(P(x,v_{\frac{n+1}{2}})\right)\cap V\left(P(v_{\frac{n+1}{2}},y)\right)=\left\{v_{\frac{n+1}{2}}\right\}.$

Proof. 

(1) The conclusion can be directly obtained by the proof of Lemma 1. (2) Both $D_{11}$ and $D_{12}$ are connected, and there is a unique path for any two different vertices in $D_{11}$ and $D_{12},$ respectively. Further, according to the definition of $D{S}_n^{\prime }\left(d\right),$ there is a unique path for any two different vertices in $D.$ For any pair of vertices $x,y$ of D such that $x\in V_{11}$ and $y\in V_{12},$ the unique path $P(x,y)$ from x to y is $x\stackrel{d_{D_{11}}(x,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}\stackrel{d_{D_{12}}(v_{\frac{n+1}{2}},y)}{\to }y.$ The unique path $P(x,v_{\frac{n+1}{2}})$ from x to $v_{\frac{n+1}{2}}$ is $x\stackrel{d_{D_{11}}(x,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}.$ The unique path $P(v_{\frac{n+1}{2}},y)$ from $v_{\frac{n+1}{2}}$ to y is $v_{\frac{n+1}{2}}\stackrel{d_{D_{12}}(v_{\frac{n+1}{2}},y)}{\to }y.$ Since $V_{11}\cap V_{12}=\left\{v_{\frac{n+1}{2}}\right\},$ we have $V\left(P(x,v_{\frac{n+1}{2}})\right)\cap V\left(P(v_{\frac{n+1}{2}},y)\right)=\left\{v_{\frac{n+1}{2}}\right\}.$ □

Definition 3.

Let $D\in D{S}_n^{\prime }\left(d\right).$ If n is odd, d is even and $d\ge 2.$ In Proposition 1, Lemma 3 and Theorem 2, we define the following notation

(1) 

$V\left(D\right)=V_{11}\cup V_{12}$ and $E\left(D\right)=E_{11}\cup E_{12}\cup E\left(L\left(D\right)\right),$ where $V_{11},V_{12},E_{11},E_{12}$ are as shown in Corollary 1.

(2) 

$V\left(U\right)=\{u:V\left(P(v_{\frac{n+1}{2}},u)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,\mathrm{where}u\in V\left(D\right)\}.$

Proposition 1.

Let $D\in D{S}_n^{\prime }\left(d\right).$ If n is odd, d is even and $d\ge 2,$ then $|V\left(U\right)\cap V_{11}|=|V\left(U\right)\cap V_{12}|=\frac{\left|V\right(U\left)\right|+1}{2}.$

Proof. 

Since n is odd and d is even, we have $v_{\frac{n+1}{2}}$ is not a loop vertex. Then, $v_{\frac{n+1}{2}}\in V\left(U\right)$ by Definition 3. Moreover, for any vertex $v_h\in V\left(U\right)$ and $h\ne \frac{n+1}{2},$ it is easy to see that $v_{n+1-h}\in V\left(U\right).$ Therefore, $\left|V\right(U\left)\right|$ is an odd number. Furthermore, we have $|V\left(U\right)\cap V_{11}|=|V\left(U\right)\cap V_{12}|=\frac{\left|V\right(U\left)\right|+1}{2}.$ □

Lemma 3.

Let $D\in D{S}_n^{\prime }\left(d\right).$ If n is odd, d is even and $d\ge 2,$ for any pair of vertices $x,z\in V\left(U\right),$ then there is a walk $W(x,z)$ from x to z such that $V\left(W\right(x,z\left)\right)\cap V\left(L\right(D\left)\right)\ne \varnothing ,$ and $\left|W\right(x,z\left)\right|\le n-d+1.$

Proof. 

Let $v_i$ be the nearest loop vertex to $v_{\frac{n+1}{2}},$ then $v_{n+1-i}$ is also the nearest loop vertex to $v_{\frac{n+1}{2}}.$ Suppose $v_i\in V_{11},$ then $v_{n+1-i}\in V_{12}.$ Let’s assume that $x\in V_{11}.$ Since $x\in V\left(U\right),$ then the path from $v_{\frac{n+1}{2}}$ to x does not pass through a loop vertex, that is $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ Let $d(x,V\left(P(v_i,v_{n+1-i})\right))=d(x,v_l),$ then $v_l\in V\left(P(v_i,v_{n+1-i})\right).$ Since $x\in V_{11},$ we have $v_l\in V\left(P(v_i,v_{\frac{n+1}{2}})\right)$. Let $d(z,V\left(P(v_i,v_{n+1-i})\right))=d(z,v_k),$ then $v_k\in V\left(P(v_i,v_{n+1-i})\right).$

Case 1 $z\in V_{11}$ and $l\ne k.$

Since $z\in V_{11},$ $v_k\in V\left(P(v_i,v_{\frac{n+1}{2}})\right).$ Let’s assume $v_k\in V\left(P(v_l,v_{\frac{n+1}{2}})\right).$ Then, there exists a walk $W(x,z)$ from x to $z,$ that is $x\stackrel{d(x,v_l)}{\to }{v}_l\stackrel{d(v_l,v_i)}{\to }{v}_i\stackrel{d(v_i,v_l)}{\to }{v}_l\stackrel{d(v_l,v_k)}{\to }{v}_k\stackrel{d(v_k,z)}{\to }z.$ We have $V\left(W(x,z)\right)\subseteq V_{11}$ by Corollary 1. Moreover, $V\left(W(x,z)\right)\cap V\left(L\left(D\right)\right)=\left\{v_i\right\}.$ Then,

$$\begin{array}{cc}\hfill & \left|W\right(x,z\left)\right|\hfill \\ \hfill =& 2d(v_i,v_l)+d(v_l,x)+d(v_l,v_k)+d(v_k,z)\hfill \\ \hfill \le & 2d(v_i,v_l)+2d(v_l,x)+2d(v_l,v_k)+2d(v_k,z)\hfill \\ \hfill \le & 2\left(\right|V\left(W(x,z)\right)|-1)\le 2(\frac{n+1}{2}-\frac{d}{2})=n-d+1.\hfill \end{array}$$

Case 2 $z\in V_{11}$ and $l=k.$

The proof is similar to Case 1, and we omit it.

Case 3 $z\in V_{12}$ and $l\ne k.$

If $z\in V_{12},$ then $v_k\in V\left(P(v_{\frac{n+1}{2}},v_{n+1-i})\right).$ Then, there exists a walk $W_1(x,z)$ from x to $z,$ that is $x\stackrel{d(x,v_l)}{\to }{v}_l\stackrel{d(v_l,v_i)}{\to }{v}_i\stackrel{d(v_i,v_l)}{\to }{v}_l\stackrel{d(v_l,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}\stackrel{d(v_{\frac{n+1}{2}},v_k)}{\to }{v}_k\stackrel{d(v_k,z)}{\to }z.$ There exists another walk $W_2(x,z)$ from x to $z,$ that is $x\stackrel{d(x,v_l)}{\to }{v}_l\stackrel{d(v_l,v_{\frac{n+1}{2}})}{\to }{v}_{\frac{n+1}{2}}\stackrel{d(v_{\frac{n+1}{2}},v_k)}{\to }{v}_k\stackrel{d(v_k,v_{n+1-i})}{\to }{v}_{n+1-i}\stackrel{d(v_{n+1-i},v_k)}{\to }{v}_k\stackrel{d(v_k,z)}{\to }z.$ We have $(V\left(W_1(x,z)\right)\cup V\left(W_2(x,z)\right))\cap V\left(L\left(D\right)\right)=\{v_i,v_{n+1-i}\}.$ Then

$$\begin{array}{cc}\hfill & |W_1(x,z)|+|W_2(x,z)|\hfill \\ \hfill =& 2d(v_i,v_l)+2d(v_l,x)+2d(v_l,v_{\frac{n+1}{2}})+2d(v_{\frac{n+1}{2}},v_k)+2d(v_k,v_{n+1-i})+2d(v_k,z)\hfill \\ \hfill =& 2d(v_{n+1-i},v_i)+2d(v_l,x)+2d(v_k,z)\hfill \\ \hfill =& 2\left(\right|V\left(W_1(x,z)\right)\cup V\left(W_2(x,z)\right)|-1)\le 2(n-d+1).\hfill \end{array}$$

We can conclude that $min\left\{\right|W_1(x,z)|,|W_2(x,z)\left|\right\}\le n-d+1.$ Then, there is a walk from x to z through a loop vertex, and the length of the walk is less than or equal to $n-d+1.$

Case 4 $z\in V_{12}$ and $l=k.$

By Corollary 1, we have $l=k=\frac{n+1}{2}$ and $V\left(P(x,v_{\frac{n+1}{2}})\right)\cap V\left(P(z,v_{\frac{n+1}{2}})\right)=\left\{v_{\frac{n+1}{2}}\right\}.$ The proof is similar to Case 3, and we omit it. □

Theorem 2.

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

(1) 

If $n\le 2d-3,$ then $k_m\left(D\right)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$

(2) 

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

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

Proof. 

We only need to consider $D\in D{S}_n^{\prime }\left(d\right).$ Since d is even, $v_{\frac{n+1}{2}}$ is not a loop vertex. We have $v_{\frac{n+1}{2}}\in V\left(U\right).$ Let x and y be any pair of vertices. By Lemma 1, we have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$

(1)

$n\le 2d-3,$ we have $n-d+1\le \frac{n-1}{2}.$ Next, we prove $\left\{v_{\frac{n+1}{2}}\right\}\subseteq N^{+}(D^{\frac{n-1}{2}}:x,y).$

Case 1.1 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

By Lemma 3, there is a walk $W(x,v_{\frac{n+1}{2}})$ from x to $v_{\frac{n+1}{2}}$ such that $V\left(W(x,v_{\frac{n+1}{2}})\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ and $\left|W\right(x,v_{\frac{n+1}{2}}\left)\right|\le n-d+1.$ There is a walk $W(y,v_{\frac{n+1}{2}})$ from y to $v_{\frac{n+1}{2}}$ such that $V\left(W(y,v_{\frac{n+1}{2}})\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ and $\left|W\right(y,v_{\frac{n+1}{2}}\left)\right|\le n-d+1.$ Since $n-d+1\le \frac{n-1}{2},$ we have $\left\{v_{\frac{n+1}{2}}\right\}\subseteq N^{+}(D^{\frac{n-1}{2}}:x,y).$

Case 1.2 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing .$

We have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}$ and $d(y,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Then, we have $\left\{v_{\frac{n+1}{2}}\right\}\subseteq N^{+}(D^{\frac{n-1}{2}}:x,y).$

Case 1.3 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Similar to Case 1.1 and Case 1.2, we have $\left\{v_{\frac{n+1}{2}}\right\}\subseteq N^{+}(D^{\frac{n-1}{2}}:x,y).$

For Case 1.1, Case 1.2 and Case 1.3, we all have $k_1(D:x,y)\le \frac{n-1}{2}.$ Since $d(v_1,v_{\frac{n+1}{2}})=d(v_n,v_{\frac{n+1}{2}}),d(v_2,v_{\frac{n+1}{2}})=d(v_{n-1},v_{\frac{n+1}{2}}),\cdots ,d(v_{\frac{n-1}{2}},v_{\frac{n+1}{2}})=d(v_{\frac{n+3}{2}},v_{\frac{n+1}{2}}).$

Therefore, we have $k_m\left(D\right)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$

(2)

$n\ge 2d-1,$ we have $n-d\ge \frac{n-1}{2}.$

Case 2.1 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

By Lemma 3, we have $V\left(U\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ For any vertex $v_h$ such that $V\left(P(v_{\frac{n+1}{2}},v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ let $v_j$ be the nearest loop vertex to $v_{\frac{n+1}{2}}$ and $v_j\in V\left(P(v_{\frac{n+1}{2}},v_h)\right).$ It is easy to find that $d(x,v_j)\le n-d$ and $d(x,v_{n+1-j})\le n-d.$ Similarly, we have $d(y,v_j)\le n-d$ and $d(y,v_{n+1-j})\le n-d.$ Then,$\{v_j,v_{n+1-j}\}\subseteq N^{+}(D^{n-d+1}:x,y).$ Further, we have $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{n-d+1+d(v_h,v_j)}:x,y).$ If $\left|V\right(U\left)\right|\ge n-2d+4,$ the conclusion is clearly established. If $\left|V\right(U\left)\right|\le n-2d+2,$ then $|V\left(U\right)\cap V_{11}|=|V\left(U\right)\cap V_{12}|=\frac{\left|V\right(U\left)\right|+1}{2}\le \frac{n-2d+3}{2}$. So, we have $d(x,v_{\frac{n+1}{2}})\le \frac{n-2d+1}{2}$ and $d(y,v_{\frac{n+1}{2}})\le \frac{n-2d+1}{2}.$ For any vertex $v_h$ such that $V\left(P(v_{\frac{n+1}{2}},v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ we have $d(x,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},v_h)\le \frac{n-2d+1}{2}+\frac{n-1}{2}=n-d$ and $d(y,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},v_h)\le n-d.$ Therefore, $k_m(D:x,y)\le n-d+1,$ where $1\le m\le n.$

Case 2.2 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing .$

We have $d(x,v_{\frac{n+1}{2}})\le \frac{n-1}{2}$ and $d(y,v_{\frac{n+1}{2}})\le \frac{n-1}{2}.$ Therefore, $k_m(D:x,y)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$ If $1\le m\le n-2d+4,$ we have $\frac{n-1}{2}+⌊\frac{m}{2}⌋\le n-d+1.$ If $n-2d+4\le m\le n,$ we have $\frac{n-1}{2}+⌊\frac{m}{2}⌋=n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉.$

Case 2.3 $V\left(P(v_{\frac{n+1}{2}},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_{\frac{n+1}{2}},y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Case 2.3.1 $\left|V\right(U\left)\right|\le n-2d+2.$

If $\left|V\right(U\left)\right|\le n-2d+2,$ then $d(y,v_{\frac{n+1}{2}})\le \frac{n-2d+1}{2}.$ For any vertex $v_h$ such that $V\left(P(v_{\frac{n+1}{2}},v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ we have $d(y,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},v_h)\le \frac{n-2d+1}{2}+\frac{n-1}{2}=n-d.$ In addition, we have $V\left(U\right)\subseteq N^{+}(D^{n-d+1}:y).$ Therefore, $N^{+}(D^{n-d+1}:y)=V\left(D\right).$ Let $V\left(H\right)=\{u:d(u,v_{\frac{n+1}{2}})\le \frac{n-2d+3}{2}\}.$ It is easy to obtain $\left|V\right(H\left)\right|\ge n-2d+4.$ For any vertex $u\in V\left(H\right),$ we have $d(x,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},u)\le \frac{n-1}{2}+\frac{n-2d+3}{2}=n-d+1.$ So, we have $V\left(H\right)\subseteq N^{+}(D^{n-d+1}:x).$ Then $V\left(H\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ For any vertex $v_h$ such that $v_h\in V\left(D\right)\backslash V\left(H\right)$, then $v_{n+1-h}\in V\left(D\right)\backslash V\left(H\right).$ We can easily conclude that $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{n-d+1+d(v_h,V\left(H\right))}:x,y).$ The conclusion is clearly established.

Case 2.3.2 $\left|V\right(U\left)\right|\ge n-2d+4.$

Suppose $V\left(W\right)=\{w:w\in V\left(U\right)\mathrm{and}d(w,v_{\frac{n+1}{2}})\le \frac{n-2d+3}{2}\}.$ It is easy to see $\left|V\right(W\left)\right|\ge n-2d+4.$ For any vertex $w\in V\left(W\right),$ we have $d(x,v_{\frac{n+1}{2}})+d(v_{\frac{n+1}{2}},w)\le \frac{n-1}{2}+\frac{n-2d+3}{2}=n-d+1.$ In addition, we have $V\left(U\right)\subseteq N^{+}(D^{n-d+1}:y).$ Therefore, $V\left(W\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ We have $k_m(D:x,y)\le n-d+1,$ where $1\le m\le \left|V\right(W\left)\right|.$ For any vertex $v_h$ such that $v_h\in V\left(D\right)\backslash V\left(W\right)$, then $v_{n+1-h}\in V\left(D\right)\backslash V\left(W\right).$ We can easily conclude that $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{n-d+1+d(v_h,V\left(W\right))}:x,y).$

Therefore, the theorem holds. □

Corollary 2.

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

(1) 

There are two connected subgraphs $D_{21}$ and $D_{22}$ of $D,$ we have $V\left(D\right)=V_{21}\cup V_{22}$ and $E\left(D\right)=E_{21}\cup E_{22}\cup \left\{(v_t,v_{n+1-f})\right\}\cup \left\{(v_{n+1-t},v_f)\right\}\cup E\left(L\left(D\right)\right).$ Where $D_{21}=(V_{21},E_{21})$ and $D_{22}=(V_{22},E_{22}),$ $V_{21}=\{v_{n+1-i}:v_i\in V_{22}\}$ and $E_{21}=\{(v_{n+1-i},v_{n+1-j}):(v_i,v_j)\in E_{22}\},$ $v_t\in V_{21}$ and $v_f\in V_{21}.$ Moreover,$|V_{21}|=|V_{22}|=\frac{n}{2},|E_{21}|=|E_{22}|=\frac{n}{2}-1.$

(2) 

If $E\left(S\right)=\varnothing ,$ then $t\ne f$ in (1). Then, there is a cycle C in $D.$ Moreover, the length of cycle C is an even number greater than or equal to $4.$

(3) 

If $E\left(S\right)\ne \varnothing ,$ then $t=f$ in (1). Then, $E\left(S\right)=\left\{(v_t,v_{n+1-t})\right\}\subseteq E\left(D\right),$ where t is an integer such that $1\le t\le n.$

Proof. 

According to Definition 1, $E\left(S\right)=\{(v_t,v_{n+1-t}):(v_t,v_{n+1-t})\in E\left(D\right),\mathrm{where}1\le t\le n\}.$ If $E\left(S\right)\ne \varnothing ,$ since $D\in D{S}_n^{\prime }\left(d\right),$ we have $\left|E\right(S\left)\right|=1.$ The conclusions can be obtained directly through the proof of Lemma 2. □

In Corollary 2, both $D_{21}$ and $D_{22}$ are connected, and there is a unique path for any two different vertices in $D_{21}$ and $D_{22},$ respectively. If $E\left(S\right)=\varnothing ,$ for any pair of vertices $u\in V_{21}$ and $v\in V_{22},$ there is more than one path from u to v. If $E\left(S\right)\ne \varnothing ,$ then there is a unique path for any two different vertices in $D.$ In fact, $E\left(S\right)\ne \varnothing$ can be regarded as a special case of $t=f$ in $E\left(S\right)=\varnothing .$

Definition 4.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is even, d is even and $d\ge 2.$ If $E\left(S\right)=\varnothing ,$ in the rest of this section, we define the following notation:

(1) 

$V\left(D\right)=V_{21}\cup V_{22}$ and $E\left(D\right)=E_{21}\cup E_{22}\cup \left\{(v_t,v_{n+1-f})\right\}\cup \left\{(v_{n+1-t},v_f)\right\}\cup E\left(L\left(D\right)\right),$ where $t\ne f,$ and $V_{21},V_{22},E_{21},E_{22},v_t,v_f$ are as shown in Corollary 2.

(2) 

A sequence of vertices in the cycle C is $v_t,\cdots ,v_f,v_{n+1-t},\cdots ,v_{n+1-f},v_t,$ where $t\ne f.$ Since $v_t\in V_{21}$ and $v_f\in V_{21},$ then $v_{n+1-t}\in V_{22}$ and $v_{n+1-f}\in V_{22}.$

(3) 

If $\{v_t,v_{n+1-t}\}\cap V\left(L\left(D\right)\right)=\varnothing ,$ let $V\left(U_1\right)=\{u:V\left(P_{D_{21}}(v_t,u)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,\mathrm{where}u\in V_{21}\}$ and $V\left(U_2\right)=\{u:V\left(P_{D_{22}}(v_{n+1-t},u)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,\mathrm{where}u\in V_{22}\}.$ Suppose $V\left(U^{\prime }\right)=V\left(U_1\right)\cup V\left(U_2\right).$

(4) 

For any vertex $u\in V_{21}.$ Let $P(u,v_t)$ be the path from u to $v_t,$ that is $u\stackrel{d_{D_{21}}(u,v_t)}{\to }{v}_t.$ Let $P(u,v_{n+1-t})$ be the path from u to $v_{n+1-t},$ that is $u\stackrel{d_{D_{21}}(u,v_f)}{\to }{v}_f\stackrel{d_D(v_f,v_{n+1-t})}{\to }{v}_{n+1-t}.$ Let $P(u,v_f)$ be the path from u to $v_f,$ that is $u\stackrel{d_{D_{21}}(u,v_f)}{\to }{v}_f.$

(5) 

For any vertex $u\in V_{22}.$ Let $P(u,v_t)$ be the path from u to $v_t,$ that is $u\stackrel{d_{D_{22}}(u,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_D(v_{n+1-f},v_t)}{\to }{v}_t.$ Let $P(u,v_{n+1-t})$ be the path from u to $v_{n+1-t},$ that is $u\stackrel{d_{D_{22}}(u,v_{n+1-t})}{\to }{v}_{n+1-t}.$ Let $P(u,v_{n+1-f})$ be the path from u to $v_{n+1-f},$ that is $u\stackrel{d_{D_{22}}(u,v_{n+1-f})}{\to }{v}_{n+1-f}.$

(6) 

If the sequence of vertices in the path $P(v_s,v_h)$ is $v_s,\cdots ,v_k,\cdots ,v_h,$ where $v_s$ and $v_h$ are any pair of vertices. Then, we define $P(v_h,v_s)$ as a sequence of vertices $v_h,\cdots ,v_k,\cdots ,v_s.$

In Definition 4, since $\{(v_f,v_{n+1-t}),(v_{n+1-f},v_t)\}\subseteq E\left(D\right),$ we have $d_D(v_f,v_{n+1-t})=d_D(v_{n+1-f},v_t)=1.$ From Definition 4, it can be seen that $|P(u,v_t)|\le \frac{n}{2}$ and $|P(u,v_{n+1-t})|\le \frac{n}{2},$ where u is any vertex of $D.$

Proposition 2.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is even, d is even and $d\ge 2.$ If $E\left(S\right)=\varnothing ,$ $v_t,v_{n+1-t}$ are the vertices on the cycle C that satisfy $\{v_t,v_{n+1-t}\}\cap V\left(L\left(D\right)\right)=\varnothing ,$ then $|V\left(U^{\prime }\right)\cap V_{21}|=|V\left(U^{\prime }\right)\cap V_{22}|=\frac{\left|V\right(U^{\prime }\left)\right|}{2}.$

Proof. 

From Definition 4, if $\{v_t,v_{n+1-t}\}\cap V\left(L\left(D\right)\right)=\varnothing ,$ for any vertex $v_h\in V\left(U^{\prime }\right),$ it’s easy to see that $v_{n+1-h}\in V\left(U^{\prime }\right).$ Therefore, $\left|V\right(U^{\prime }\left)\right|$ is even. Further, we have $|V\left(U^{\prime }\right)\cap V_{21}|=|V\left(U^{\prime }\right)\cap V_{22}|=\frac{\left|V\right(U^{\prime }\left)\right|}{2}.$ □

Lemma 4.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is even, d is even and $d\ge 2.$ Let x be any vertex of $D.$ Suppose $E\left(S\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ then

(1)

If $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,$ we have $|P(x,v_t)|\le \frac{\left|V\right(U^{\prime }\left)\right|}{2}.$

(2)

$V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $V\left(P(v_{n+1-t},x)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Proof. 

Suppose $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Case 1 $x\in V_{21}.$

Let $d_{D_{21}}(x,V\left(P_{D_{21}}(v_t,v_f)\right))=d_{D_{21}}(x,v_l),$ where $v_l\in V\left(P_{D_{21}}(v_t,v_f)\right).$ Then $P(x,v_t)$ is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_t)}{\to }{v}_t.$ Moreover, $P(x,v_f)$ is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_f)}{\to }{v}_f.$ Since $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ it is easy to see that $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $V\left(P(x,v_f)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Since $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,$ then $V\left(P(x,v_t)\right)\subseteq V\left(U_1\right).$ We have $|P(x,v_t)|=|V\left(P(x,v_t)\right)|-1\le |V\left(U_1\right)|-1=\frac{\left|V\right(U^{\prime }\left)\right|}{2}-1.$ Moreover, $P(x,v_{n+1-t})$ is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_f)}{\to }{v}_f\stackrel{d_D(v_f,v_{n+1-t})}{\to }{v}_{n+1-t}.$ Since $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ then $V\left(P(x,v_{n+1-t})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Case 2 $x\in V_{22}.$

Let $d_{D_{22}}(x,V\left(P_{D_{22}}(v_{n+1-t},v_{n+1-f})\right))=d_{D_{22}}(x,v_k),$ where $v_k\in V\left(P_{D_{22}}\right(v_{n+1-t},$ $v_{n+1-f}\left)\right).$ Then $P(x,v_{n+1-f})$ is $x\stackrel{d_{D_{22}}(x,v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,v_{n+1-f})}{\to }{v}_{n+1-f}.$ Moreover, $P(x,v_{n+1-t})$ is $x\stackrel{d_{D_{22}}(x,v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,v_{n+1-t})}{\to }{v}_{n+1-t}.$ Since $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ we can easily see that $V\left(P(x,v_{n+1-f})\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $V\left(P(x,v_{n+1-t})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

$P(x,v_t)$ is $x\stackrel{d_{D_{22}}(x,v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_D(v_{n+1-f},v_t)}{\to }{v}_t.$ Since $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,$ then $V\left(P(x,v_{n+1-f})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ Let u be any vertex such that $u\in V\left(P(x,v_{n+1-f})\right).$ Since $V\left(P(x,v_{n+1-f})\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ we have $V\left(P(u,v_{n+1-t})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ Then $V\left(P(x,v_{n+1-f})\right)\subseteq V\left(U_2\right).$ Therefore, $|P(x,v_t)|=|V\left(P(x,v_{n+1-f})\right)|\le |V\left(U_2\right)|=\frac{\left|V\right(U^{\prime }\left)\right|}{2}.$ Since $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ then $V\left(P(x,v_{n+1-t})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

For $V\left(P(v_{n+1-t},x)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,$ we have $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ The proof is similar to $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing ,$ so let us omit it. □

By the proof of Lemma 4, we directly get Corollary 3.

Corollary 3.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is even, d is even and $d\ge 2.$ Suppose $E\left(S\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ then

(1) 

Let x be any vertex of $D,$ then $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $x\in V\left(U^{\prime }\right).$

(2) 

If $x\in V_{21},$ then $V\left(P(x,v_f)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $V\left(P(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

(3) 

If $x\in V_{22},$ then $V\left(P(x,v_{n+1-f})\right)\cap V\left(L\left(D\right)\right)=\varnothing$ if and only if $V\left(P(x,v_{n+1-t})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

Lemma 5.

Let $D\in D{S}_n^{\prime }\left(d\right),$ where n is even, d is even and $d\ge 2.$ For any pair of vertices $x,z\in V\left(U^{\prime }\right),$ if

(1) 

$E\left(S\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing .$

(2) 

$E\left(S\right)=\left\{(v_t,v_{n+1-t})\right\}$ and $\{v_t,v_{n+1-t}\}\cap V\left(L\left(D\right)\right)=\varnothing .$

For the above two cases, then there is a walk $W(x,z)$ from x to z such that $V\left(W\right(x,z\left)\right)\cap V\left(L\right(D\left)\right)\ne \varnothing ,$ and $\left|W\right(x,z\left)\right|\le n-d+1.$

Proof. 

Case 1 $E\left(S\right)=\varnothing$ and $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing .$

A sequence of vertices in the cycle C is $v_t,\cdots ,v_f,v_{n+1-t},\cdots ,v_{n+1-f},v_t.$ Let $v_i$ be the nearest loop vertex to $v_t,$ where $v_i\in V_{21}.$ Let $v_{n+1-j}$ be the nearest loop vertex to $v_{n+1-f},$ where $v_{n+1-j}\in V_{22}.$ Let x be any vertex such that $x\in V_{21}.$ Since $x\in V\left(U^{\prime }\right),$ then the path in $D_{21}$ from x to $v_t$ doesn’t pass through a loop vertex, that is $V\left(P_{D_{21}}(x,v_t)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ Let $d_{D_{21}}(x,V\left(P_{D_{21}}(v_t,v_i)\right))=d_{D_{21}}(x,v_l),$ where $v_l\in V\left(P_{D_{21}}(v_t,v_i)\right).$ Let z be any vertex such that $z\in V\left(U^{\prime }\right).$

Case 1.1 $z\in V_{21}.$

Let $d_{D_{21}}(z,V\left(P_{D_{21}}(v_t,v_i)\right))=d_{D_{21}}(z,v_k),$ then $v_k\in V\left(P_{D_{21}}(v_t,v_i)\right).$ Let us assume $v_k\in V\left(P_{D_{21}}(v_t,v_l)\right)$ and $k\ne l,$ then there exists a walk $W(x,z)$ from x to $z,$ that is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_i)}{\to }{v}_i\stackrel{d_{D_{21}}(v_i,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_k)}{\to }{v}_k\stackrel{d_{D_{21}}(v_k,z)}{\to }z.$ We have $V\left(W(x,z)\right)\subseteq V_{21}$ by Corollary 2. Moreover, $V\left(W(x,z)\right)\cap V\left(L\left(D\right)\right)=\left\{v_i\right\}.$ Then,

$$\begin{array}{cc}\hfill & \left|W\right(x,z\left)\right|\hfill \\ \hfill =& 2d_{D_{21}}(v_i,v_l)+d_{D_{21}}(v_l,x)+d_{D_{21}}(v_l,v_k)+d_{D_{21}}(v_k,z)\hfill \\ \hfill \le & 2d_{D_{21}}(v_i,v_l)+2d_{D_{21}}(v_l,x)+2d_{D_{21}}(v_l,v_k)+2d_{D_{21}}(v_k,z)\hfill \\ \hfill \le & 2\left(\right|V\left(W(x,z)\right)|-1)\le 2(\frac{n}{2}-\frac{d}{2})=n-d.\hfill \end{array}$$

For $k=l,$ similarly, there is a walk from x to z through a loop vertex, and the length of the walk is less than or equal to $n-d.$

Case 1.2 $z\in V_{22}.$

Let $d_{D_{22}}(z,V\left(P_{D_{22}}(v_{n+1-f},v_{n+1-j})\right))=d_{D_{22}}(z,v_k),$ then $v_k\in V\left(P_{D_{22}}(v_{n+1-f},v_{n+1-j})\right).$ From Corollary 3, since $z\in V\left(U^{\prime }\right),$ then $V\left(P_{D_{22}}(z,v_{n+1-f})\right)\cap V\left(L\left(D\right)\right)=\varnothing .$ So, we have $V\left(P_{D_{22}}(z,v_k)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

There exists a walk $W_1(x,z)$ from x to $z,$ that is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_i)}{\to }{v}_i\stackrel{d_{D_{21}}(v_i,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_t)}{\to }{v}_t\stackrel{d_D(v_t,v_{n+1-f})}{\to }{v}_{n+1-f}\stackrel{d_{D_{22}}(v_{n+1-f},v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,z)}{\to }z.$ There exists another walk $W_2(x,z)$ from x to $z,$ that is $x\stackrel{d_{D_{21}}(x,v_l)}{\to }{v}_l\stackrel{d_{D_{21}}(v_l,v_t)}{\to }{v}_t\stackrel{d_D(v_t,v_{n+1-f})}{\to }{v}_{n+1-f}$ $\stackrel{d_{D_{22}}(v_{n+1-f},v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,v_{n+1-j})}{\to }{v}_{n+1-j}\stackrel{d_{D_{22}}(v_{n+1-j},v_k)}{\to }{v}_k\stackrel{d_{D_{22}}(v_k,z)}{\to }z.$ Since $(v_t,v_{n+1-f})\in E\left(D\right),$ then $d_D(v_t,v_{n+1-f})=1.$ We have $(V\left(W_1(x,z)\right)\cup V\left(W_2(x,z)\right))\cap V\left(L\left(D\right)\right)=\{v_i,v_{n+1-j}\}.$ Then

$$\begin{array}{cc}\hfill & |W_1(x,z)|+|W_2(x,z)|\hfill \\ \hfill =& 2d_{D_{21}}(v_i,v_l)+2d_{D_{21}}(v_l,x)+2d_{D_{21}}(v_l,v_t)+2\hfill \\ \hfill +& 2d_{D_{22}}(v_{n+1-f},v_k)+2d_{D_{22}}(v_k,v_{n+1-j})+2d_{D_{22}}(v_k,z)\hfill \\ \hfill =& 2\left(\right|V\left(W_1(x,z)\right)\cup V\left(W_2(x,z)\right)|-1)\le 2(n-d+1).\hfill \end{array}$$

We can conclude that $min\left\{\right|W_1(x,z)|,|W_2(x,z)\left|\right\}\le n-d+1.$

For any pair of vertices $x,z$ in D such that $x,z\in V\left(U^{\prime }\right),$ there is a walk from x to z through a loop vertex, and the length of the walk is less than or equal to $n-d+1.$

Case 2 $E\left(S\right)=\left\{(v_t,v_{n+1-t})\right\}$ and $\{v_t,v_{n+1-t}\}\cap V\left(L\left(D\right)\right)=\varnothing .$

For $E\left(S\right)=\left\{(v_t,v_{n+1-t})\right\}\subseteq E\left(D\right),$ it is equivalent to $t=f$ in Case 1, let us omit the proof. □

Theorem 3.

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

(1) 

If $n\le 2d-2,$ then $k_m\left(D\right)\le \frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$

(2) 

If $n\ge 2d,$ then

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

Proof. 

We only need to consider $D\in D{S}_n^{\prime }\left(d\right).$ Let us consider $E\left(S\right)=\varnothing .$

Case 1 $V\left(C\right)\cap V\left(L\right(D\left)\right)\ne \varnothing .$

Suppose $\{v_g,v_{n+1-g}\}\subseteq V\left(C\right)\cap V\left(L\left(D\right)\right),$ where $v_g\in V_{21}.$ Let x be any vertex. By Lemma 2, we have $d(x,v_g)\le \frac{n}{2}$ and $d(x,v_{n+1-g})\le \frac{n}{2}.$ Then, we have $\{v_g,v_{n+1-g}\}\subseteq N^{+}(D^{\frac{n}{2}}:x).$ For any vertex $v_h$ such that $v_h\in V_{21},$ we have $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{\frac{n}{2}+d_{D_{21}}(v_h,v_g)}:x).$ Then, $k_m\left(D\right)\le \frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$

(1)

If $n\le 2d-2,$ the conclusion is obvious.

(2)

If $n\ge 2d,$ for $1\le m\le n-2d+4,$ we have $\frac{n}{2}-1+⌈\frac{m}{2}⌉\le n-d+1.$ For $n-2d+4\le m\le n,$ we have $\frac{n}{2}-1+⌈\frac{m}{2}⌉=n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉.$ The conclusion is established.

Case 2 $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing .$

By Lemma 5, for any pair of vertices $x,z$ in D such that $x,z\in V\left(U^{\prime }\right),$ there is a walk from x to z through a loop vertex, and the length of the walk is less than or equal to $n-d+1.$ Since $V\left(C\right)\cap V\left(L\right(D\left)\right)=\varnothing ,$ for any vertex $x\in V\left(D\right)$ such that $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ we have $V\left(P(v_{n+1-t},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ by Lemma 4. Furthermore, we have $|P(x,v_t)|\le \frac{n}{2}$ and $|P(x,v_{n+1-t})|\le \frac{n}{2}.$

Let $x,y$ be any pair of vertices satisfying that $x,y\in V\left(D\right).$

(1)

$n\le 2d-2,$ we have $n-d+1\le \frac{n}{2}.$ Obviously, $\{v_t,v_{n+1-t}\}\subseteq V\left(U^{\prime }\right).$ Further, $\{v_t,v_{n+1-t}\}\subseteq N^{+}(D^{\frac{n}{2}}:x,y).$ Then, $k_m(D:x,y)\le \frac{n}{2},$ where $1\le m\le 2.$ For any vertex $v_h$ such that $v_h\in V_{21},$ we have $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{\frac{n}{2}+d_{D_{21}}(v_h,v_t)}:x,y).$ Therefore, we have $k_m\left(D\right)\le \frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$

(2)

$n\ge 2d,$ we have $n-d\ge \frac{n}{2}.$

Case 2.1 $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)=\varnothing$ and $V\left(P(v_t,y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

By Lemma 5, we have $V\left(U^{\prime }\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ For any vertex $v_h\in V_{21}$ such that $V\left(P(v_t,v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ let $v_s$ be the nearest loop vertex to $v_t$ and $v_s\in V\left(P(v_t,v_h)\right).$ It’s easy to get $\{v_s,v_{n+1-s}\}\subseteq N^{+}(D^{n-d}:x,y).$ Therefore, we have $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{n-d+1+d_{D_{21}}(v_h,v_s)}:x,y).$ If $\left|V\right(U^{\prime }\left)\right|\ge n-2d+4,$ the conclusion is clearly established. If $\left|V\right(U^{\prime }\left)\right|\le n-2d+2,$ according to Lemma 4, we have $|P(x,v_t)|\le \frac{\left|V\right(U^{\prime }\left)\right|}{2}\le \frac{n-2d+2}{2}.$ Similarly, $|P(y,v_t)|\le \frac{n-2d+2}{2}.$ For any vertex $v_h$ such that $V\left(P(v_t,v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ we have $|P(x,v_t)|+|P(v_t,v_h)|\le \frac{n-2d+2}{2}+\frac{n}{2}=n+1-d$ and $|P(y,v_t)|+|P(v_t,v_h)|\le n+1-d.$ Therefore, $k_m(D:x,y)\le n-d+1,$ where $1\le m\le n.$

Case 2.2 $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_t,y)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing .$

By Lemma 4, we have $V\left(P(v_{n+1-t},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_{n+1-t},y)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing .$ We have $|P(x,v_t)|\le \frac{n}{2}$ and $|P(y,v_t)|\le \frac{n}{2}.$ Further, we have $|P(x,v_{n+1-t})|\le \frac{n}{2}$ and $|P(y,v_{n+1-t})|\le \frac{n}{2}.$ Therefore, $k_m\left(D\right)\le \frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$ If $1\le m\le n-2d+4,$ we have $\frac{n}{2}-1+⌈\frac{m}{2}⌉\le n-d+1.$ If $n-2d+4\le m\le n,$ we have $\frac{n}{2}-1+⌈\frac{m}{2}⌉=n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉.$

Case 2.3 $V\left(P(v_t,x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing$ and $V\left(P(v_t,y)\right)\cap V\left(L\left(D\right)\right)=\varnothing .$

By Lemma 4, $V\left(P(v_{n+1-t},x)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing .$ We have $V\left(U^{\prime }\right)\subseteq N^{+}(D^{n-d+1}:y)$ by Lemma 5. Moreover, $|P(v_t,x)|\le \frac{n}{2}$ and $|P(v_{n+1-t},x)|\le \frac{n}{2}.$

Case 2.3.1 $\left|V\right(U^{\prime }\left)\right|\le n-2d+2.$

Then, $|P(y,v_t)|\le \frac{n-2d+2}{2}.$ For any vertex $v_h$ such that $V\left(P(v_t,v_h)\right)\cap V\left(L\left(D\right)\right)\ne \varnothing ,$ we have $|P(y,v_t)|+|P(v_t,v_h)|\le \frac{n-2d+2}{2}+\frac{n}{2}=n-d+1.$ In addition, we have $V\left(U^{\prime }\right)\subseteq N^{+}(D^{n-d+1}:y).$ Therefore, $N^{+}(D^{n-d+1}:y)=V\left(D\right).$ Let $V\left(H_{11}\right)=\{u:|P(u,v_t)|\le \frac{n-2d+2}{2},\mathrm{where}u\in V_{21}\}.$ Let $V\left(H_{12}\right)=\{u:|P(u,v_{n+1-t})|\le \frac{n-2d+2}{2},\mathrm{where}u\in V_{22}\}.$ Suppose $V\left(H_1\right)=V\left(H_{11}\right)\cup V\left(H_{12}\right).$ It is easy to get $\left|V\right(H_1\left)\right|\ge n-2d+4.$ For any vertex $u\in V\left(H_{11}\right),$ then $|P(x,v_t)|+|P(v_t,u)|\le \frac{n}{2}+\frac{n-2d+2}{2}=n-d+1.$ For any vertex $u\in V\left(H_{12}\right),$ then $|P(x,v_{n+1-t})|+|P(v_{n+1-t},u)|\le \frac{n}{2}+\frac{n-2d+2}{2}=n-d+1.$ Furthermore, we have $V\left(H_1\right)\subseteq N^{+}(D^{n-d+1}:x).$ Then $V\left(H_1\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ For any vertex $v_h$ such that $v_h\in V\left(D\right)\backslash V\left(H_1\right)$, then $v_{n+1-h}\in V\left(D\right)\backslash V\left(H_1\right).$ We can easily conclude that $\{v_h,v_{n+1-h}\}\subseteq N^{+}$ $(D^{n-d+1+d(v_h,V\left(H_1\right))}:x,y).$ The conclusion is clearly established.

Case 2.3.2 $\left|V\right(U^{\prime }\left)\right|\ge n-2d+4.$

Let $V\left(W_{11}\right)=\{w:w\in V\left(U_1\right),\mathrm{and}|P(w,v_t)|\le \frac{n-2d+2}{2}\}.$ Let $V\left(W_{12}\right)=\{w:w\in V\left(U_2\right),\mathrm{and}|P(w,v_{n+1-t})|\le \frac{n-2d+2}{2}\}.$ Suppose $V\left(W_1\right)=V\left(W_{11}\right)\cup V\left(W_{12}\right).$ It is easy to see $\left|V\right(W_1\left)\right|\ge n-2d+4.$ For $w\in V\left(W_{11}\right),$ we have $|P(x,v_t)|+|P(v_t,w)|\le \frac{n}{2}+\frac{n-2d+2}{2}=n-d+1.$ For $w\in V\left(W_{12}\right),$ we have $\left|P\right(x,v_{n+1-t}\left)\right|+$ $|P(v_{n+1-t},w)|\le \frac{n}{2}+\frac{n-2d+2}{2}=n-d+1.$ Therefore, $V\left(W_1\right)\subseteq N^{+}(D^{n-d+1}:x,y).$ We have $k_m(D:x,y)\le n-d+1,$ where $1\le m\le \left|V\right(W_1\left)\right|.$ For any vertex $v_h$ such that $v_h\in V\left(D\right)\backslash V\left(W_1\right)$, then $v_{n+1-h}\in V\left(D\right)\backslash V\left(W_1\right).$ We have $\{v_h,v_{n+1-h}\}\subseteq N^{+}(D^{n-d+1+d(v_h,V\left(W_1\right))}:x,y).$

For $E\left(S\right)\ne \varnothing ,$ it is equivalent to $t=f$ in $E\left(S\right)\ne \varnothing$, let us omit the proof.

Therefore, the theorem holds. □

4. The $\mathit{m}$-Competition Indices of ${\mathit{M}}_{\mathit{n},\mathit{d}}$

Definition 5.

Let $M_{n,d}$ be the digraph with the vertex set $\{v_1,v_2,\cdots ,v_n\}$ and the arc set $E\left(M_{n,d}\right)=\{v_i\leftrightarrow v_{i+1}|1\le i\le n-1\}\cup E\left(L\left(M_{n,d}\right)\right),$ where $1\le d\le n.$ Let $E\left(L\left(M_{n,d}\right)\right)=\{(v_i,v_i):(v_{n+1-i},v_{n+1-i})\in E\left(L\left(M_{n,d}\right)\right),\mathrm{where}1\le i\le n\}$ and $\left|E\right(L\left(M_{n,d}\right)\left)\right|=d.$ Then, $E\left(L\left(M_{n,d}\right)\right)$ represents the set of d loops, and the loops appear in pairs.

By Definition 5, we have $M_{n,d}\in D{S}_n^{\prime }\left(d\right)$ (see Figure 1 and Figure 2).

Remark 3.

In Figure 2, n can be either odd or even. That is to say, if n is odd, d is even and $d\ge 2,$ $M_{n,d}$ in Theorem 5 is shown in Figure 2. Moreover, If n is even, d is even and $d\ge 2,$ $M_{n,d}$ in Theorem 6 is also shown in Figure 2.

Theorem 4.

If n is odd and d is odd, then $k_m\left(M_{n,d}\right)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$

Proof. 

$M_{n,d}$ is shown in Figure 1. By Theorem 1, we have $k_m\left(M_{n,d}\right)\le \frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$ It is easy to find that $k_1\left(M_{n,d}\right)=k_1(M_{n,d}:v_1,v_n)=\frac{n-1}{2}.$ For $1\le a\le \frac{n-1}{2},$ we have $N^{+}(D^{\frac{n-1}{2}+a}:v_1,v_n)=\{v_{\frac{n-1}{2}+1-a},v_{\frac{n-1}{2}+2-a},\cdots ,v_{\frac{n-1}{2}+1+a}\}.$ Therefore, $k_m\left(M_{n,d}\right)=k_m(M_{n,d}:v_1,v_n)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$ □

Theorem 5.

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

(1)

If $n\le 2d-3,$ then $k_m\left(M_{n,d}\right)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$

(2)

If $n\ge 2d-1,$ then $k_m\left(M_{n,d}\right)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $n-2d+4\le m\le n.$

Proof. 

$M_{n,d}$ is shown in Figure 2.

(1)

If $n\le 2d-3,$ the proof is similar to Theorem 4, and we omit it.

(2)

If $n\ge 2d-1,$ by Theorem 2, we have $k_m\left(M_{n,d}\right)\le n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉,$ where $n-2d+4\le m\le n.$ If $n-2d+4\le m\le n,$ we have $\frac{n-1}{2}+⌊\frac{m}{2}⌋=n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉.$ It is easy to get that $k_m(M_{n,d}:v_1,v_n)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $1\le m\le n.$ Therefore, $k_m\left(M_{n,d}\right)=k_m(M_{n,d}:v_1,v_n)=\frac{n-1}{2}+⌊\frac{m}{2}⌋,$ where $n-2d+4\le m\le n.$

□

Theorem 6.

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

(1) 

If $n\le 2d-2,$ then $k_m\left(M_{n,d}\right)=\frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$

(2) 

If $n\ge 2d,$ then $k_m\left(M_{n,d}\right)=\frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $n-2d+4\le m\le n.$

Proof. 

$M_{n,d}$ is shown in Figure 2.

(1)

By Theorem 3, we have $k_m\left(M_{n,d}\right)\le \frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$ It is easy to find that $k_i\left(M_{n,d}\right)=k_i(M_{n,d}:v_1,v_n)=\frac{n}{2},$ where $1\le i\le 2.$ For $1\le a\le \frac{n}{2}-1,$ we have $N^{+}(D^{\frac{n}{2}+a}:v_1,v_n)=\{v_{\frac{n}{2}-a},v_{\frac{n}{2}+1-a},\cdots ,v_{\frac{n}{2}+1+a}\}.$ Therefore, for $1\le m\le n,$ we have $k_m\left(M_{n,d}\right)=k_m(M_{n,d}:v_1,v_n)=\frac{n}{2}-1+⌈\frac{m}{2}⌉.$

(2)

By Theorem 3, we have $k_m\left(M_{n,d}\right)\le n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉,$ where $n-2d+4\le m\le n.$ For $n-2d+4\le m\le n,$ we have $\frac{n}{2}-1+⌈\frac{m}{2}⌉=n-d+1+⌈\frac{m-(n-2d+4)}{2}⌉.$ It is easy to find that $k_m(M_{n,d}:v_1,v_n)=\frac{n}{2}-1+⌈\frac{m}{2}⌉,$ where $1\le m\le n.$ Therefore, for $n-2d+4\le m\le n,$ we have $k_m\left(M_{n,d}\right)=k_m(M_{n,d}:v_1,v_n)=\frac{n}{2}-1+⌈\frac{m}{2}⌉.$

□

Let $D\in D{S}_n\left(d\right).$ Combining the conditions of Theorem 4, Theorem 5(1) and Theorem 6(1), if n and d satisfy one of the following (1) or (2):

(1)

n is odd and d is odd.

(2)

$n\le 2d-2$ and d is even such that $d\ge 2.$

Then the upper bounds of $k_m\left(D\right)$ can be attained as D is isomorphic to $M_{n,d},$ where $1\le m\le n.$

5. Conclusions

In this paper, we get the upper bounds for the m-competition indices of $D{S}_n\left(d\right)$, where $1\le m\le n.$ Let D be isomorphic to $M_{n,d}.$ If n and d satisfy that n is odd and d is odd, or $n\le 2d-2$ and d is even such that $d\ge 2,$ then the upper bounds for the m-competition indices of $D{S}_n\left(d\right)$ can be reached by D, where $1\le m\le n.$ However, the digraphs whose m-competition indices reach the upper bounds are not completely determined. For a general doubly symmetric primitive digraph, its upper bounds on the m-competition indices are not given. It is meaningful to solve this problem in further research.