\betaegin{document}

\title{{f Exponents of the primitive Boolean matrices with fixed girth}

\betaegin{abstract}
The $girth$ of a primitive Boolean matrix is defined to be the $girth$ of its associated digraph. In this paper, among all primitive Boolean matrices of order $n$, the primitive exponents of those of girth $g$ are considered. For the primitive matrices of both order $n\gammaeq 10$ and girth $g>\frac{n^{2}-4n}{4(n-3)}$, the matrices with primitive exponents in $[2n-2 +(g- 1)(n-3), n+g(n-2)]$ are completely characterized.

\betaigskip
\noindent {\betaf AMS Classification:} 05C50, 15B35

\noindent {\betaf Keywords:} Primitive exponent; Girth
\end{abstract}

\sigmaection{Introduction}

\ \ \ \ We adopt the standard conventions, notations and definitions for
Boolean matrices, their entries,
arithmetics, powers and primitivity. The reader who is not familiar with these
matters is referred to \cite{BLiu}--\cite{LB1} and \cite{JYS}.

In this paper, we permit loops but no multiple arcs in a
digraph. For a digraph $S$, we denote by $V(S)$ the vertex set and denoted by $E(S)$ the
arc set.

\betaegin{definition} \lambdaabel{de1.2.2}
Let $A$ be a square $(0,1)$-Boolean matrix of order $n$. The {\it
associated digraph} of $A$, denoted by $D(A)$, has vertex set $V
=\{1$, $2$, $\cdots$, $n\}$ and arc set $E=\{(i, \ j)|\, a_{ij}\neq 0
\}$.
\end{definition}

For a digraph $S$, the {\it associated $(0,1)$-Boolean matrix} of $S$, denoted by $A_{S}$, is a square $(0,1)$-Boolean matrix $A$ with $D(A)$=$S$.
Denoted by $exp(S)$ the primitive $exponent$ of a primitive digraph $S$.
For a primitive $(0,1)$-Boolean $A$, we denote by $exp(A)$ its primitive $exponent$. From combinatorial matrix theory, we know that for a primitive $(0,1)$-Boolean $A$, $exp(A) = exp(D(A))$, and for a primitive digraph $S$, $exp(S)=exp(A_{S})$. As a result, the digraphs can be used to study the primitivity of the $(0,1)$-Boolean matrices.

Primitivity of a square $(0,1)$-Boolean matrix
is of great significance, which is
closely related to many other problems in various areas of pure and
applied mathematics (see \cite{5}, \cite{Kim}, \cite{LB1}, \cite{39},
\cite{55}). In practice, we consider the {\it memoryless
communication system} \cite{39} in communication field, which is
depicted as a digraph $D$ of order $n$. Suppose that each vertex
controls a different piece of information at time $t=0$. At the time
$t=1$, for any vertex $v\in V(D)$, the information $\sigmaigma_{v}$
controlled by vertex $v$ is communicated to each vertex in
$N^{+}(v)$ ({\it out-neighbors}), but $v$ ``forgets" the
information. Proceeding like this, we can ensure that each vertex in
$D$ receives the $n$ pieces of different information at sometime $t$
if $D$ is primitive, where the least time $t$ such that each vertex
in $D$ receive the $n$ pieces of different information is equal to
the primitive exponent of $D$. So, studying the primitvity
of the digraphs is very useful in
information communication field.

It is known that an important topic about the primitivity of the Boolean matrices is to determine the primitivity of a given class of Boolean matrices including the extremal exponents and exponents distribution. Some interesting results about this topic have been shown in many references (see \cite{LB1}, for instance).

Because there is no ambiguity in this paper, for convenience, a directed walk, a directed
path and a directed cycle is abbreviated into a walk, a path and a cycle, respectively. The $girth$ of a strongly connnected digraph, denoted by $g$, is the length of the shortest cycle in this digraph. The $girth$ of a primitive Boolean matrix is defined to be the $girth$ of its associated digraph. In this paper, among all primitive Boolean matrices of order $n$, we consider the primitive exponents of those of girth $g$. For the primitive matrices of both order $n\gammaeq 10$ and girth $g>\frac{n^{2}-4n}{4(n-3)}$, the matrices with primitive exponents in $[2n-2 +(g- 1)(n-3), n+g(n-2)]$ are completely characterized.
\sigmaection{Preliminaries}

~~~~In this section, some notations and working lemmas are introduced.

\betaegin{definition} \lambdaabel{de2.1}
Let $\{s_{1}$, $s_{2}$, $\cdots$, $s_{\lambdaambda} \}$ be a set of
distinct positive integers with
 gcd$(s_{1}$, $s_{2}$, $\cdots$, $s_{\lambdaambda})$ = 1. The Frobenius number of $
s_{1}$, $s_{2}$, $\cdots$, $s_{\lambdaambda} $, denoted by $\psihi(s_{1},
s_{2}, \cdots, s_{\lambdaambda})$, is the smallest nonnegative integer $m$
such that for any nonnegative integers $k\gammaeq m$, there are nonnegative
integers $a_{i} \ (i = 1, 2, \cdots, \lambdaambda)$ such that $k=\sigmaum
\lambdaimits_{i = 1}^ \lambdaambda$ $ a_{i}s_{i}$.
\end{definition}

It is well known that
if gcd$(s_{1}, s_{2}) = 1$, then $\psihi(s_{1}, s_{2}) = (s_{1} -
1)(s_{2} - 1)$ (see \cite{LB1}, for examlpe).
From Definition \rhoef {de2.1}, it is easy to see that if there exist
$s_{i}, s_{j}\in\{ s_{1}$, $s_{2}$, $\cdots$, $s_{\lambdaambda} \}$ such
that gcd$(s_{i}, s_{j}) = 1$, then $\psihi(s_{1},
s_{2},\cdots,s_{\lambdaambda})\lambdaeq \psihi(s_{i}, s_{j})$. If $\min \{s_{i}|\, 1\lambdaeq i\lambdaeq
\lambdaambda\} = 1$, then $\psihi(s_{1}, s_{2},\cdots,s_{\lambdaambda})=0$.

In a primitive digraph $S$, the distance from $v_{i}$ to $v_{j}$, denoted by $d(v_{i}, v_{j})$ or $d_{S}(v_{i}, v_{j})$, is the length of the shortest path from $v_{i}$ to $v_{j}$. We denote by $C_{k}$ or {\it $k$-cycle} a cycle with length $k$, and denote by $C(S)$ the cycle length set of digraph $S$. Suppose $C(S)=\{p_{1}$, $p_{2}$,
$\lambdadots$, $p_{u}\}$. Let $d_{C(S)}(v_{i}$, $v_{j})$ denote the
length of the shortest walk from $v_{i}$ to $v_{j}$ which meets at
least one $p_{i}$-cycle for each $i$, where $i=1$, $2, \cdots, u$. Such a
shortest directed walk is called a $C(S)$-walk from $v_{i}$ to
$v_{j}$. Further, let $d(C(S))=\max\{d_{C(S)}(v_{i}$,
$v_{j})|\, v_{i}$, $v_{j}\in V(S)\}$.

\betaegin{lemma}{\betaf \cite{BLiu}} \lambdaabel{le2.2}
Let $S$ be a primitive digraph of order $n$
  and $C(S)=\{p_{1}$, $p_{2}$, $\lambdadots$, $p_{u}\}$.
  Then we have $exp(S)\lambdaeq d(C(S))+\psihi(p_{1},p_{2},\lambdadots,p_{u})$.
\end{lemma}

The
union of digraphs $H$ and $G$ is the digraph $G\cup H$ with
vertex set $V(G)\cup V(H)$
 and arc set $E(G)\cup E(H)$. The
$standard$ $n$-$cycle$ is defined to be $\mathscr{C}=(v_{n}$, $v_{n-1}$, $\cdots$ , $v_{2}$,
$v_{1}$, $v_{n})$. Let $D_1=\mathscr{C}\cup(v_{1}$, $v_{n-1})$ and $D_{2}$ =
$D_{1}\cup (v_{2}$, $v_{n})$.

\betaegin{lemma}{\betaf \cite{5}} \lambdaabel{le2.3}
Let $S$ be a primitive digraph of both order $n$ and girth $g$. Then $exp(S)\lambdaeq n+g(n-2)$.
\end{lemma}

\betaegin{lemma}{\betaf \cite{HWL}} \lambdaabel{le2.4}
Let $S$ be a primitive digraph of order $n$.

$\mathrm{(i)}$ $exp(S)= (n-1)^{2}+1$ if and only if $S\cong D_{1}$;

$\mathrm{(ii)}$ $exp(S)= (n-1)^{2}$ if and only if $S\cong D_{2}$.
\end{lemma}

Lemma \rhoef{le2.3} gives an upper bound for the primitive exponent of a digraph with both order $n$ and girth $g$. Because a digraph with both order $n$ and girth $n-1$ is isomorphic to $D_{1}$ or $D_{2}$,  from Lemma \rhoef{le2.4}, we see that the digraphs with both order $n$ and girth $n-1$ are completely characterized.  But for those with girth less than $n-1$, this problem is unsolved as far.

\betaegin{lemma}{\betaf \cite{MiaoZhang}} \lambdaabel{le2.5}
Let $S$ be a primitive digraph of order $n$ and $|C(S)|\gammaeq 3$. Then
$exp(S)\lambdaeq \lambdafloor\frac{(n-2)^{2}}{2}\rhofloor+n$.
\end{lemma}

From Lemma \rhoef{le2.5}, we get the following corollary.

\betaegin{corollary}\lambdaabel{cl2.1}
Let $S$ be a primitive digraph of order $n$. If $exp(S)> \lambdafloor\frac{(n-2)^{2}}{2}\rhofloor+n$, then $|C(S)|= 2$.
\end{corollary}

\betaegin{lemma}{\betaf \cite{SKK}} \lambdaabel{le2.6}
Let $S$ be a primitive directed graph on $n$ vertices having
cycles of just two lengths, $g$ and $q$, where without loss of generality we take
$g\lambdaeq q$. Then $exp(S) \lambdaeq 2n -g - 1 + (g- 1)(q - 1)$.
\end{lemma}

\sigmaection{Main results}

\betaegin{lemma}\lambdaabel{th3.2}
Let $S$ be a primitive digraph of order $n\gammaeq 6$. If $C(S)=\{g, q\}$ where $1\lambdaeq g< q\lambdaeq n-1$, then $exp(S)\lambdaeq 2n-2 +(g- 1)(n-3)$.
\end{lemma}

\betaegin{proof}
Note that $2n - g- 1 + (g- 1)(q - 1)=2n-2 +(g- 1)(q - 2)$, and $f(q)=2n-2 +(g- 1)(q - 2)$ is  monotone nondecreacing with respect to $q$. By Lemma \rhoef{le2.6}, the result follows as desired.  $\ \ \ \ \Box$

\end{proof}

Let $n$, $g$ be two positive integers satisfying $\gammacd(n, g)=1$, and let $t=\min\{n-g+1, g\}$, $F=\{1, 2, 3, \lambdadots, t\}$. Let $N\sigmaubseteq F$, $D_{g, N}=\mathscr{C}\cup_{i\in N}(v_{i}$,
$v_{g+i-1})$ (see Fig. 3.1).

\unitlength 1mm \lambdainethickness{0.4pt}
\betaegin{picture}(94.33,37.33)
\betaezier{156}(41.33,20.00)(39.33,6.67)(65.00,7.33)
\betaezier{172}(41.33,20.00)(39.33,36.67)(65.00,35.00)
\betaezier{176}(65.33,35.00)(93.33,36.33)(91.33,20.33)
\betaezier{168}(91.33,20.33)(92.33,5.67)(65.33,7.33)
\psiut(61.00,7.33){\lambdaine(5,3){30.00}}
\psiut(84.33,9.33){\lambdaine(-2,3){17.11}}
\psiut(49.33,8.67){\circle*{1.49}} \psiut(91.00,15.33){\circle*{1.49}}
\psiut(61.33,7.33){\circle*{1.49}} \psiut(84.33,9.33){\circle*{1.49}}
\psiut(91.33,25.33){\circle*{1.33}} \psiut(67.67,35.00){\circle*{1.49}}
\psiut(41.67,15.33){\circle*{1.49}} \psiut(41.33,25.67){\circle*{1.33}}
\psiut(48.00,9.33){\vector(-2,1){3.00}}
\psiut(41.33,15.67){\vector(0,1){5.67}}
\psiut(42.33,28.00){\vector(3,4){1.75}}
\psiut(52.67,34.67){\vector(1,0){5.33}}
\psiut(68.00,35.00){\vector(1,0){6.33}}
\psiut(91.33,25.33){\vector(0,-1){6.67}}
\psiut(86.00,32.00){\vector(4,-3){3.00}}
\psiut(90.33,14.33){\vector(-2,-3){1.78}}
\psiut(74.33,7.33){\vector(-1,0){4.33}}
\psiut(60.67,7.33){\vector(-1,0){4.67}}
\psiut(49.33,8.67){\lambdaine(6,1){41.67}}
\psiut(49.33,9.00){\vector(1,0){3.00}}
\psiut(81.33,19.33){\vector(3,2){4.67}}
\psiut(77.67,19.67){\vector(-2,3){2.00}}
\psiut(47.67,6.33){\makebox(0,0)[cc]{$v_{1}$}}
\psiut(39.00,15.00){\makebox(0,0)[cc]{$v_{n}$}}
\psiut(37.00,25.67){\makebox(0,0)[cc]{$v_{n-1}$}}
\psiut(61.33,4.00){\makebox(0,0)[cc]{$v_{2}$}}
\psiut(85.33,7.00){\makebox(0,0)[cc]{$v_{i}$}}
\psiut(94.50,14.00){\makebox(0,0)[cc]{$v_{g}$}}
\psiut(96.83,26.00){\makebox(0,0)[cc]{$v_{g+1}$}}
\psiut(67.33,38.33){\makebox(0,0)[cc]{$v_{g+i-1}$}}
\psiut(65.67,-2.00){\makebox(0,0)[cc]{Fig. 3.1. $D_{g, N}$}}
\end{picture}

\betaegin{theorem}\lambdaabel{th3.3}
Let $r=\max\{u\, |\, u\in N\}$. Then $\mbox{exp}(D_{g,
N})=(n-2)g+1-r+n$.

\end{theorem}

\betaegin{proof}
{\betaf  Case 1}  $r<n-g+1$. Then $g+r-1< n$ and $d(C(D_{g, N}))=d_{C(D_{g,
N})}(v_{n},v_{g+r})=2n-g-r.$ By Lemma \rhoef{le2.2}, we get
$$\mbox{exp}(D_{g, N})\lambdaeq
d(C(D_{g, N}))+\psihi(n, g)=2n-g-r+(n-1)(g-1)=(n-2)g+1-r+n.\ $$

Next, we prove $\mbox{exp}(D_{g, N})=2n-g-r+(n-1)(g-1)$. To prove this, we prove that there is no walk of length
$2n-g-r+(n-1)(g-1)-1$ from $v_{n}$ to $v_{g+r}$. Otherwise,
suppose $W$ is a walk of length $2n-g-r+(n-1)(g-1)-1$ from
$v_{n}$ to $v_{g+r}$. Let $\mathcal {P}$ denote the path from $v_{n}$ to
$v_{g+r}$ on cycle $\mathscr{C}$. Denote by $L(\mathcal {P})$ the length of $\mathcal {P}$. Then $L(\mathcal {P})= d(v_{n},
v_{g+r})=n-g-r$ and $\mathcal {P}$ meet only $n$-cycle $\mathscr{C}$ but not any
$g$-cycle. $W$ must contain $\mathcal {P}\cup \mathscr{C}$, some
$g$-cycles and some times of $\mathscr{C}$, that is,
$$2n-g-r+(n-1)(g-1)-1=n-g-r+n+a_{1}n+a_{2}g\ \ (a_{j}\gammaeq
0,\ j=1,2).$$ This induces $\psihi(n,g)-1=a_{1}n+a_{2}g\ \ (a_{j}\gammaeq 0,\
j=1,2)$, which contradicts the definition of $\psihi(n,g)$. As a result, there is no walk of length
$2n-g-r+(n-1)(g-1)-1$ from $v_{n}$ to $v_{g+r}$. Then
$\mbox{exp}(D_{g, N})=2n-g-r+(n-1)(g-1)$ follows.

{\betaf Case 2}  $r=n-g+1$. Then $g+r-1=n$ and $d(C(D_{g, N}))=d_{C(D_{g,
N})}(v_{n},v_{1})=n-1.$ Analogous to Case 1, we get
$\mbox{exp}(D_{g, N})=
(n-1)g=(n-2)g+1-r+n.$ $\ \ \ \Box$
\end{proof}

Let $n$, $g$ ($n\gammaeq 2g$) be two positive integers satisfying $\gammacd(n, g)=1$. Let $H$ consist of $n$-cycle $(v_{1}$, $v_{2}$, $\lambdadots$, $v_{n}$, $v_{1})$ and two $g$-cycles where the two $g$-cycles have no common vertex (see Fig. 3.2). Denote by $C^{1}=(v_{1}$, $v_{2}$, $\lambdadots$, $v_{g}$, $v_{1})$ and $C^{2}=(v_{k}$, $v_{k+1}$, $\lambdadots$, $v_{k+g-1}$, $v_{k})$ the two $g$-cycles in $H$ where $k\gammaeq g+1$, $g+k-1\lambdaeq n$.

\sigmaetlength{\unitlength}{0.7pt}
\betaegin{center}
\betaegin{picture}(200,206)
\psiut(37,104){\circle*{4}}
\psiut(35,137){\circle*{4}}
\psiut(167,64){\circle*{4}}
\qbezier(34,120)(34,87)(56,64)\qbezier(56,64)(79,42)(112,42)\qbezier(112,42)(144,42)(167,64)
\qbezier(167,64)(190,87)(190,120)\qbezier(34,120)(34,152)(56,175)\qbezier(56,175)(79,198)(112,198)
\qbezier(112,198)(144,198)(167,175)\qbezier(167,175)(190,152)(190,120)
\psiut(116,42){\circle*{4}}
\psiut(160,181){\circle*{4}}
\psiut(56,65){\circle*{4}}
\qbezier(167,64)(102,84)(37,104)
\psiut(63,182){\circle*{4}}
\psiut(188,125){\circle*{4}}
\qbezier(63,182)(125,154)(188,125)
\psiut(15,105){$v_{1}$}
\psiut(168,53){$v_{g}$}
\psiut(13,142){$v_{n}$}
\psiut(37,58){$v_{2}$}
\psiut(193,120){$v_{k}$}
\psiut(25,192){$v_{k+g-1}$}
\qbezier(39,145)(41,159)(44,172)
\psiut(70,-9){Fig. 3.2. $H$}
\qbezier(39,145)(47,156)(55,166)
\qbezier(188,106)(180,95)(173,84)
\qbezier(188,106)(188,94)(188,81)
\qbezier(119,197)(129,192)(139,187)
\qbezier(119,197)(131,199)(143,200)
\qbezier(140,146)(128,148)(117,150)
\qbezier(140,146)(132,155)(125,163)
\qbezier(68,63)(74,57)(81,50)
\qbezier(81,50)(71,52)(62,54)
\qbezier(110,82)(118,76)(127,70)
\qbezier(110,82)(121,82)(132,81)
\end{picture}
\end{center}

\betaegin{lemma}\lambdaabel{le3.4}
$\mbox{exp}(H)\lambdaeq(n-1)g+n-2g$.

\end{lemma}

\betaegin{proof}
To prove this lemma, we consider the following two cases.

{\betaf  Case 1}  $d(v_{g+k-1},v_{1})= 1$ and $d(v_{g},v_{k})= 1$. Now, $n=2g$, $k=g+1$, $g+k-1=n$, and $d(C(H))=d_{C(H)}(v_{1},v_{n})=n-1.$ By Lemma \rhoef{le2.2}, we get
$$\mbox{exp}(H)\lambdaeq
d(C(H))+\psihi(n, g)=n-1+(n-1)(g-1)=(n-1)g.\ $$

{\betaf  Case 2}  $\max\{d(v_{g+k-1},v_{1})$, $d(v_{g},v_{k})\}\gammaeq 2$. Then $2g+1\lambdaeq n$. If $d(v_{g+k-1},v_{1})=\max\{d(v_{g+k-1},v_{1})$, $d(v_{g},v_{k})\}$. Then $g+k\lambdaeq n$, and $d(C(H))=d_{C(H)}(v_{g+k},v_{n})=n-g-k+n=2n-g-k.$ By Lemma \rhoef{le2.2}, we get
$$\mbox{exp}(H)\lambdaeq
(n-1)(g-1)+2n-g-k=(n-1)g+n-g-k+1.$$
If $d(v_{g},v_{k})=\max\{d(v_{g+k-1},v_{1})$, $d(v_{g},v_{k})\}$, then $k-g\gammaeq2$ and $d(C(H))=d_{C(H)}(v_{g+1},v_{k-1})=k-g-2+n.$ In a same way, we get
$$\mbox{exp}(H)\lambdaeq
(n-1)(g-1)+k-g-2+n=(n-1)g+k-g-1.$$ Note that $k-g-1\lambdaeq n-2g$, $n-k-g+1\lambdaeq n-2g$.
Then the result follows.
$\ \ \ \Box$
\end{proof}

Let $D^{r}=\{D_{g,
N}\, |\, N\sigmaubseteq F, \max\{u\, |\, u\in N\}=r\}$. From Theorem \rhoef{th3.3}, we see that for every digraph $S\in D^{r}$, we have $\mbox{exp}(S)=(n-2)g+1-r+n$.

\betaegin{theorem}\lambdaabel{th3.6}
 Suppose $\mathrm{gcd}(g, n) = 1$. Let $S$ be a primitive digraph of both order $n\gammaeq 10$ and girth $g>\frac{n^{2}-4n}{4(n-3)}$, and let $2n-2 +(g- 1)(n-3)< w\lambdaeq n+g(n-2)$, $z=(n-2)g+1+n-w$. If $exp(S)=w$, then $S$ is isomorphic to one in $D^{z}$.

\end{theorem}

\betaegin{proof}
Note that $2n-1 +(g- 1)(n-3)>\lambdafloor\frac{(n-2)^{2}}{2}\rhofloor+n$. By Corollary \rhoef{cl2.1}, it follows that $C(S)=\{g, q\}$. Note that by Lemma \rhoef{th3.2}, if $q\lambdaeq n-1$, then $\mbox{exp}(S)\lambdaeq 2n-2 +(g- 1)(n-3)$. Hence, it follows that $q=n$. It is known that for a primitive diagraph $G$ and its a primitive spanning subgraph $D$, it follows that $exp(G)\lambdaeq exp(D)$. Note that $\frac{n^{2}-4n}{4(n-3)}\gammaeq 2$. So, $g\gammaeq 3$. Note that if $n\gammaeq 2g$, then $(n-1)g+n-2g< 2n-1 +(g- 1)(n-3)$. This means that $S$ has no subgraph isomorphic to $H$. Then the result follows from Theorem \rhoef{th3.3}. $\ \ \ \Box$
\end{proof}

Noting the relation between Boolean matrices and digraphs, we have the following corollary.

\betaegin{corollary}\lambdaabel{th3.7}
 Suppose $\mathrm{gcd}(g, n) = 1$. Let $A$ be a primitive Boolean matrix of both order $n\gammaeq 10$ and girth $g>\frac{n^{2}-4n}{4(n-3)}$, and let $2n-2 +(g- 1)(n-3)< w\lambdaeq n+g(n-2)$, $z=n+1+g(n-2)-w$. If $exp(A)=w$, then $D(A)$ is isomorphic to one in $D^{z}$.

\end{corollary}

Let $Q_{1}= D_{g, N}$ for $N=\{1\}$, $Q_{2}= D_{g, N}$ for $N=\{1, 2\}$. Note that $D^{1}= \{Q_{1}\}$ and $D^{2}= \{Q_{2}\}$. Then we have the following corollary.

\betaegin{corollary}\lambdaabel{th3.8}
 Suppose $\mathrm{gcd}(g, n) = 1$. Let $A$ be a primitive digraph of both order $n\gammaeq 10$ and girth $g>\frac{n^{2}-4n}{4(n-3)}$. Then

 $\mathrm{(i)}$ $\mbox{exp}(A)=(n-2)g+n$ if and only if $D(A)\cong Q_{1}$;

  $\mathrm{(ii)}$ $\mbox{exp}(A)=(n-2)g+n-1$ if and only if $D(A)\cong Q_{2}$.

\end{corollary}

\noindent{\betaf Acknowledgment}

We offer many thanks to the referees for their kind reviews and
helpful suggestions.

\sigmamall {
\betaegin{thebibliography}{99}

\betaibitem {BLiu} R. Brualdi, B. Liu, Generalized Exponents of
primitive directed graphs, {\it J. of Graph Theory.} 14 (1994)
483--499

\betaibitem{5} A. Dulmage, N. Mendelsohn, Graphs and
            matrices, {\it Graph Theory and Theoretical Physics}, Ed.
        by F.Harary, Academic Press, 1967.

\betaibitem {ZYY} Z. He, P. Yuan, L. You, On the exponent set of nonnegative primitive tensors, {\it Linear Algebra
Appl.,} 465 (2015) 376-390.

\betaibitem {JGHRSV} J. Holladay, R. Varga, On powers of nonnegative matrices, Proc, Amer, Math. Soc., 1958,
  9:631--634.

\betaibitem {Kim} K. Kim, Boolean Matrix Theory and Applications,
  Marcel Dekkez, New York (1982).

\betaibitem {SKK} S. Kirkland, A note on the eigenvalues of a primitive matrix With large exponent, {\it Linear Algebra
Appl.,} 253 (1997), 103-112.

\betaibitem {LB1} B. Liu, Combinatorical matrix theory, second published, {\it Science
Press}, Beijing, 2005.

\betaibitem{39} J. Ljubic, Estimates of the number of states that
             arise in the determinization of a nondeterministic
         autonomous automaton, {\it Dokl. Akad. Nauk SSSR,}
         155 (1964), 41--43.

\betaibitem {MiaoZhang} Z. Miao and K. Zhang, The local exponent sets of
primitive digraphs, {\it Linear Algebra Appl.,} 307 (2000) 15--33.

\betaibitem{55} S. Schwarz, On the semigroup of binary relations on a
             finite set, {\it Czech. Math. J.,} 20 (95) (1970)
         632--679.

\betaibitem {JYS} J. Shao, On a conjuncture about the exponent set of primitive matrices, {\it Linear Algebra
Appl.,} 65 (1985), 91-123.

\betaibitem {HWL} H. Wieland, Unzenlegbare, nicht negative matrizen. Math. Z., 52 (1952), 642--648.

\end{thebibliography}
}

\end{document}