J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
1Ae19.
VERTEX EXPONENTS OF A CLASS OF
TWO-COLORED HAMILTONIAN DIGRAPHS
Aghni Syahmarani1 and Saib Suwilo2 Department of Mathematics.
University of Sumatera Utara.
Indonesia Department of Mathematics.
University of Sumatera Utara.
Indonesia, saib@usu.
Abstract.
A two-colored digraph D.
is primitive provided there are nonnegative integers h and k such that for each pair of not necessarily distinct vertices u and v in D.
there exists a .
, .
-walk in D.
from u to v.
The exponent of a primitive twocolored digraph D.
, exp(D.
), is the smallest positive integer h k taken over all such nonnegative integers h and k.
The exponent of a vertex v in D .
is the smallest positive integer s t such that for each vertex u in D.
there is an .
, .
-walk from .
v to u.
We study the vertex exponents of primitive two-colored digraphs Ln on n Ou 5 vertices whose underlying digraph is the Hamiltonian digraph consisting of the cycle v1 Ie vn Ie vnOe1 Ie A A A Ie v2 Ie v1 and the arc v1 Ie vnOe2 .
For such .
two-colored digraph it is known that 2n2 Oe 6n 2 O exp(Ln ) O .
3 Oe 2n2 .
/2.
We show that if exp(Ln ) = .
3 Oe 2n2 .
/2, then its vertex exponents lie on .
3 Oe 2n2 Oe 3n .
/4, .
3 Oe 2n2 3n .
and if exp(Ln ) = 2n2 Oe 6n 2, then its vertex exponents lie on .
2 Oe 4n 5, n2 Oe 2n Oe .
Key words: Two-colored digraph, primitive digraph, exponent, vertex exponent, hamiltonian digraph.
2000 Mathematics Subject Classification: 05C15, 05C20.
Received: 28-10-2012, revised: 09-01-2012, accepted: 17-01-2012.
Syahmarani and Suwilo Abstrak.
Digraf dwiwarna D.
adalah primitif dengan syarat terdapat bilangan bulat nonnegatif h dan k sehingga untuk setiap pasangan yang tidak perlu berbeda titik u dan v di D .
terdapat sebuah jalan .
, .
di D.
dari u ke v.
Eksponen dari primitif digraf dwiwarna D.
, yang dinotasikan dengan exp(D.
), adalah bilangan bulat positif terkecil h k dari semua jumlahan yang mungkin bilangan bulat nonnegatif h dan k .
Eksponen dari sebuah titik v di D.
adalah bilangan bulat positif terkecil s t sehingga untuk tiap titik u di D.
terdapat sebuah jalan .
, .
dari v ke u.
Pada paper ini akan dipelajari eksponen titik dari digraf dwiwarna primitif Ln pada n Ou 5 titik dengan digraf dasar adalah digraf Hamilton yang memuat lingkaran v1 Ie vn Ie vnOe1 Ie A A A Ie v2 Ie v1 dan busur v1 Ie vnOe2 .
Untuk .
digraf dwiwarna yang demikian telah diketahui bahwa 2n2 Oe 6n 2 O exp(Ln ) O 3 Oe 2n2 .
/2.
Paper ini menunjukkan bahwa jika exp(Ln ) = .
3 Oe 2n2 .
/2, maka eksponen titiknya berada pada [.
3 Oe 2n2 Oe 3n .
/4, .
3 Oe 2n2 3n .
dan jika exp(Ln ) = 2n2 Oe 6n 2, maka eksponen titiknya berada pada .
2 Oe 4n 5, n2 Oe 2n Oe .
Kata kunci: Digraf dwiwarna, digraf primitif, eksponen, eksponen titik, digraf Hamilton.
Introduction Given a vector x we use the notation x Ou 0 to show that x is a nonnegative vector, that is, a vector each of whose entry is nonnegative.
Thus for two vectors x and y, the notion x Ou y means that x Oe y Ou 0.
A digraph D is strongly connected provided for each pair of vertices u and v in D there is a uv-walk from u to v.
A ministrong digraph is a strongly digraph such that removal of any single arc will result in a not strongly connected digraph.
A strongly connected digraph D is primitive provided there exists a positive integer Ee such that for every pair of not necessarily distinct vertices u and v in D there is a walk from u to v of length Ee.
The smallest of such positive integer Ee is the exponent of D denoted by exp(D).
By a two-colored digraph D.
we mean a digraph D such that each of it arcs is colored by either red or blue but not both colors.
An .
, .
-walk in D.
is a walk of length s t consisting of s red arcs and t blue arcs.
For a walk w we denote r.
to be the number of red arcs in w and b.
to be the .
of blue r.
arcs in w.
The length of w is Ee.
= r.
and the vector is the b.
composition of the walk w.
A two-colored digraph D.
is primitive provided there exist nonnegative integers h and k such that for each pair of vertices u and v in D.
there is an .
, .
-walk from u to v.
The smallest of such positive integer h k is the exponent of D.
and is denoted by exp(D.
Researches on exponents of two-colored digraphs can be found in .
, 3, 5, .
Let D.
be a strongly connected two-colored digraph and suppose that the set of all cycles in D.
is C = {C1 .
C2 , .
Cq }.
We deAne a cycle matrix of D.
Vertex Exponents to be a 2 by q matrix r(C1 ) b(C1 ) r(C2 ) A A A b(C2 ) A A A r(Cq ) b(Cq ) that is M is a matrix such that its ith column is the composition of the ith cycle Ci , i = 1, 2, .
, q.
If the rank of M is 1, the content of M is deAned to be 0, and the content of M is deAned to be the greatest common divisors of the 2 by 2 minors of M , otherwise.
The following result, due to Fornasini and Valcher .
, gives an algebraic characterization of a primitive two-colored digraph.
Theorem 1.
Let D.
be a strongly connected two-colored digraph with at least one arc of each color.
Let M be a cycle matrix of D.
The two-colored digraph D.
is primitive if and only if the content of M is 1.
Let D.
be a two-colored digraph on n vertices v1 , v2 , .
, vn .
Gao and Shao .
deAne a more local concept of exponents of two-colored digraphs as follows.
For any vertex vk in D.
, k = 1, 2, .
, n, the exponent of the vertex vk , denoted by D.
k ), is the smallest positive integer p1 p2 such that for every vertex v in D.
there is a .
1 , p2 )-walk from vk to v.
It is customary to order the vertices v1 , v2 , .
vn of D.
such that D.
1 ) O D.
2 ) O A A A O D.
n ).
Gao and Shao .
discuss the vertex exponents for primitive two-colored digraphs of Wielandt type, that is a Hamiltonial digraph consisting of the cycle v1 Ie vn Ie vnOe1 Ie vnOe2 Ie A A A Ie v2 Ie v1 and the arcs v1 Ie vnOe1 .
Their results show that if the twocolored Wielandt digraph W .
has only one blue arc va Ie vaOe1 , a = 2, 3, .
, nOe1, then D.
k ) = n2 Oe 2n k Oe a 1.
If the two-colored Wielandt digraph has two blue arcs then D.
k ) = n2 Oe 2n k or D.
k ) = n2 Oe 2n k 1.
Suwilo .
discusses the vertex exponents of two-colored ministrong digraphs D.
on n vertices whose underlying digraph is the primitive extremal ministrong digraph D with exp(D) = n2 Oe 4n 6.
We present formulae for vertex exponent of two-colored digraphs whose underlying digraph is the Hamiltonian digraph consisting of the cycle v1 Ie vn Ie vnOe1 Ie vnOe2 Ie A A A Ie v2 Ie v1 and the arc v1 Ie vnOe2 where n is an odd integer with n Ou 5.
In Section 2 we discuss previous result on exponent of two-colored Hamiltonian digraph.
In Section 3 we present a way in setting up a lower and an upper bound for vertex exponents.
We use these results in Section 4 to And vertex exponents for the class of two-colored Hamiltonian digraphs.
Two-colored Hamiltonian Digrahs It is a well known result, see .
, that the largest exponent of a primitive two-colored digraph lies on the interval [.
3 Oe 2n2 .
/2, .
n3 2n2 Oe 2.
when n is odd and lies on the interval [.
3 Oe 5n2 7n Oe .
/2, .
n3 Oe 2n2 Oe 2.
when n is even.
The left end of the Arst interval is obtained using two-colored digraphs Syahmarani and Suwilo consisting of two cycles whose underlying digraph is the primitive Hamiltonian digraph Ln on n Ou 5 vertices which consists of an n-cycle v1 Ie vn Ie vnOe1 Ie vnOe2 Ie vnOe3 Ie A A A Ie v2 Ie v1 and the arc v1 Ie vnOe2 as shown in Figure 1.
Notice that the digraph Ln consists of exactly two cycles, they are the n-cycle and the .
Oe .
-cycle v1 Ie vnOe2 Ie vnOe3 Ie A A A Ie v2 Ie v1 .
Since Ln is primitive, it is necessary that .
n is odd.
Let Ln be a two-colored digraph with underlying digraph is Ln .
Let M be the cycle matrix of Ln .
By Theorem 1.
1 the following lemma, see .
, .
proof, gives necessary and suEcient condition for Ln to be a primitive two-colored vnOe4
AvnOe3
a A nOe2
vnOe1
sA v
AAU
A v2 CWA v1 Av Figure 1.
Digraph Ln with underlying digraph Ln .
Lemma 2.
, .
Let Ln be a two-colored digraph .
Oe .
/2 .
/2 .
The digraph Ln is primitive if and only if M = .
Oe .
/2 .
Oe .
/2 The following theorem, due Suwilo .
see also Shader and Suwilo .
, gives the lower and upper bound for exponent of class of two-colored digraphs whose underlying digraph is the digraph Ln .
Theorem 2.
, .
Let Ln be a two-colored digraph with underlying digraph Ln .
Then 2n2 Oe 6n 2 O exp(Ln ) O .
3 Oe 2n2 .
/2.
Furthermore Suwilo .
characterizes necessary and suEcient conditions for .
two-colored digraphs Ln to have exp(Ln ) = .
3 Oe 2n2 .
/2 and to have .
exp(Ln ) = 2n2 Oe 6n 2, respectively.
Corollary 2.
Let Ln be a two-colored digraph with underlying digraph Ln .
The exp(Ln ) = .
3 Oe2n2 .
/2 if and only if Ln has a red path of length .
/2 and a blue path of length .
Oe .
/2.
Corollary 2.
Let Ln be a two-colored digraph with underlying digraph Ln .
The exp(Ln ) = 2n2 Oe 6n 2 if and only if Ln has a unique .
, .
-path and this path lies on both cycles.
Vertex Exponents .
Lemma 2.
1 implies that for a two-colored digraph Ln to be primitive, the n-cycles must contain exactly .
/2 red arcs and the .
Oe .
-cycle must contain exactly .
Oe .
/2 red arcs.
Corollary 2.
3 implies that for the two-colored digraph Ln to have exponent .
3 Oe 2n2 .
/2, the n-cycle must contain a red path of length .
/2 and a blue path of length .
Oe .
/2.
This implies there are four possible two-colored digraph Ln with exponent .
3 Oe 2n2 .
/2.
We characterize them as follows.
A The two-colored digraph Ln is of Type I if the red arcs of Ln are the arcs that lie on the path vn Ie vnOe1 Ie vnOe2 Ie A A A Ie v.
Oe.
/2 of length .
/2 plus the arc v1 Ie vnOe2 .
A The two-colored digraph Ln is of Type II if the red arcs of Ln are the arcs that lie on the path v.
Oe.
/2 Ie v.
Oe.
/2 Ie A A A Ie 1 Ie vn Ie vnOe1 of length .
/2 plus the arc v1 Ie vnOe2 .
A The two-colored digraph Ln is of Type i if the red arcs of Ln are the arcs that lie on the path v.
/2 Ie v.
Oe.
/2 Ie A A A Ie 2 Ie 1 Ie vn of length .
/2.
A The two-colored digraph Ln is of Type IV if the red arcs of Ln are the arcs that lie on the path vnOe1 Ie vnOe2 Ie A A A Ie v.
Oe.
/2 of length .
/2.
Considering Corollary 2.
4, we have exp(Ln ) = 2n2 Oe 6n 2 if and only if .
, .
-path in Ln is the path a Ie a Oe 1 Ie a Oe 2 for some 3 O a O n Oe 2.
In Section 4 for two-colored digraphs Ln with exp(Ln ) = .
3 Oe 2n2 .
/2 we show that the exponents of its vertices lie on [.
3 Oe 2n2 Oe 3n .
/4, .
3 Oe 2n2 For two-colored digraphs whose exp(Ln ) = 2n2 Oe 6n 2 we show that the exponents of its vertices lie on .
2 Oe 4n 5, n2 Oe 2n Oe .
Bounds for vertex exponents In this section, a way in setting up an upper and a lower bound for vertex exponents of two-colored digraphs is discussed.
We start with the lower bound of vertex exponent especially for primitive two-colored digraphs consisting of two We assume through out that the exponent of vertex vk , k = 1, 2, .
, n is obtained using .
, .
-walks.
Lemma 3.
Let D.
be a primitive two-colored digraph consisting of two Let vk be a vertex in[ D.
] and suppose ] there is an .
, .
-walk from vk to each vertex vj in D.
with = M for some nonnegative integers q1 ] q2 r.
k,j ) and q2 .
Then Ou M Oe1 for some path pk,j from vk to vj .
k,j ) Syahmarani and Suwilo Let vk be a vertex in D.
We note that from Lemma 3.
1 for the vertex vk and any vertex vj in D we have ] [ r.
k,j ) b(C2 )r.
k,j ) Oe r(C2 )b.
k,j ) Oe1 OuM b.
k,j ) r(C1 )b.
k,j ) Oe b(C1 )r.
k,j ) If for some vertex vj we have b(C2 )r.
k,j ) Oe r(C2 )b.
k,j ) Ou 0, then we deAne u0 = b(C2 )r.
k,j ) Oe r(C2 )b.
k,j ) .
If for some vertex vi we have r(C1 )b.
k,i ) Oe b(C1 )r.
k,i ) Ou 0, then we deAne v0 = r(C1 )b.
k,i ) Oe b(C1 )r.
k,i ) .
By Lemma 3.
1 we have q1 Ou u0 and q2 Ou v0 .
This implies [ ] OuM and hence s t Ou .
(C1 ) b(C1 ))u0 .
(C2 ) b(C2 ))v0 = Ee(C1 )u0 Ee(C2 )v0 .
We have proved the following theorem.
Theorem 3.
Let D.
be a primitive two-colored digraph consisting of two cycles C1 and C2 and let vk be a vertex in D.
For some vertex vi and vj in D.
] u0 [= b(C ] 2 )r.
k,j ) Oe r(C2 )b.
k,j ) and v0 = r(C1 )b.
k,i ) Oe b(C1 )r.
k,i ).
Then OuM and hence D.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 .
We now discuss a way in setting up an upper bound.
First we consider upper bound for exponents of certain vertices two-colored digraph consisting two cycles.
Proposition 3.
Let D.
be a primitive two-colored digraph consisting of two cycles C1 and C2 .
Suppose vk be a vertex of D.
that belongs to both cycles C1 and C2 .
If for each i = 1, 2, .
, n and for some positive integers s and t, there is a path pk,i from vk to vi such that the system
] [ ]
k,i ) Mx k,i ) has nonnegative integer solution, then D.
k ) O s t.
Proof.
Assume that the solution to the system .
is x = .
1 , x2 )T .
Since D.
is primitive, then M is invertible and hence x1 and x2 cannot be both zero.
We note that vk belongs to both cycles and we consider three cases.
If x1 , x2 > 0, then the walk that starts at vk , moves x1 and x2 times around the cycles C1 and C2 respectively and back at vk , and then moves to vi along the path pk,i is an .
, .
-walk from vk to vi .
If x1 = 0 and x2 > 0, then the walk that starts at vk , moves x2 times around the cycle C2 and back at vk , then moves to vertex vi along the path pk,i is an .
, .
-walk from vk to vi .
Similarly if x1 > 0 and x2 = 0, then then the walk that starts at vk , moves x1 times around the cycle C1 Vertex Exponents and back at vk , then moves to vertex vi along the path pk,i is an .
, .
-walk from vk to vi .
Therefore for every vertex vi , i = 1, 2, .
, n there is an .
, .
-walk from vk to vi .
The deAnition of exponent of vertex vk implies that D.
k ) O s t.
Proposition 3.
4 gives an upper bound of a vertex exponent in term of the vertex exponent of a speciAed vertex.
We deAne d.
k , .
to be the distance from vk to v, that is the length of a shortest walk from vk to v.
Proposition 3.
Let D.
be a primitive two-colored digraph on n vertices.
Let v be a vertex in D.
with exponent D.
For any vertex vk , k = 1, 2, .
, n in D.
we have D.
k ) O D.
k , .
The vertex exponents In this section we discuss the vertex exponents of class of two-colored digraphs .
Ln whose underlying digraph is the digraph Ln in Figure 1.
We Arst discuss the .
case where exp(Ln ) = .
3 Oe 2n2 .
/2.
Let vk be a vertex in Ln and suppose that the red path of length .
/2 has xO and yO as its initial and terminal vertex.
We use the the path pk,yO from vk to yO to determine the value of u0 = b(C2 )r.
k,yO ) Oe r(C2 )b.
k,yO ) in equation .
We use the path pk,xO from vk to xO in order to determine the value of v0 = r(C1 )b.
k,xO ) Oe b(C1 )r.
k,xO ) in equation .
We assume that L.
k ) is obtained using .
, .
-walks and we split our discussion into four parts depending on the type of the two-colored digraph Ln .
Lemma 4.
For the two-colored digraph Ln of type I we have L.
k ) = .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, n.
Proof.
We Arst show that L.
k ) Ou .
3 Oe2n2 Oen .
/4 k for all k = 1, 2, .
, n.
Since the red path of length .
/2 in Ln is the path vn Ie vnOe1 Ie A A A Ie v.
Oe.
/2 , we set xO = vn and y O = v.
Oe.
/2 .
We split the proof into two cases.
Case 1: 1 O k O .
Oe .
/2 Taking yO = v.
Oe.
/2 , we see that there are two paths from vk to v.
Oe.
/2 .
They are an (.
/2, .
-path and an (.
Oe .
/2, k Oe .
-path.
Using the (.
/2, .
-path pk,.
Oe.
/2 from vk to v.
Oe.
/2 and the deAnition of u0 in equation .
we And = b(C2 )r.
Oe.
/2 Oe r(C2 )b.
Oe.
/2 ) nOe1 n2 Oe 1 k.
Syahmarani and Suwilo Using the (.
Oe .
/2, k Oe .
-path pk,.
Oe.
/2 from vk to v.
Oe.
/2 and the deAnition of u0 in equation .
we have = b(C2 )r.
Oe.
/2 Oe r(C2 )b.
Oe.
/2 ) nOe1 nOe1 n2 3 k.
Oe .
= Oe From equations .
we conclude that u0 = .
2 Oe .
/4 Oe k.
/2.
Taking xO = vn , there is a unique path pk,n from vk to vn which is a .
, .
Using this path and the deAnition of v0 in equation .
we have = r(C1 )b.
k,n ) Oe b(C1 )r.
k,n ) nOe1 nOe3 kOe .
= k.
Oe .
/2 By Theorem 3.
2 we have [ ] OuM
[ ]
[ 2
Oe .
/4 Oe k.
/2 k.
Oe .
/2 [ 3
Oe n Oe n .
/8 .
3 Oe 3n2 Oe n 3 8.
/8 .
Therefore, we conclude that L.
k ) = s t Ou .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, .
Oe .
/2.
Case 2: .
/2 O k O n Taking y O = v.
Oe.
/2 , then there is a unique path pk,.
Oe.
/2 from vk to v.
Oe.
/2 which is a .
Oe .
Oe .
/2, .
-path.
Using this path and considering the deAnition of u0 in equation .
we have u0 = k.
Oe .
/2 Oe .
Oe .
2 /4.
Taking xO = vn , there is a unique path pk,n from vk to vn .
This path is a .
Oe .
Oe .
/2, .
Oe .
-path.
Using this path and the deAnition of v0 in equation .
we get v0 = .
Oe .
n Oe .
/4 Oe k.
Oe .
/2.
By Theorem 3.
2 we get k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
3 Oe 2n2 Oe n .
/4 k for all k = .
/2, .
/2, .
, n.
Combining .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe n .
/4 k.
for all k = 1, 2, .
, n.
We next show the upper bound, that is L.
k ) O .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, n.
We Arst show that L.
1 ) = .
3 Oe 2n2 Oe n .
/4 1 and then we use Proposition 3.
4 in order to determine the upper bound for exponents of other vertices.
From .
it is known that L.
1 ) Ou .
3 Oe 2n2 Oe n .
/4 1.
Thus, it remains to show that L.
1 ) O .
3 Oe 2n2 Oe n .
/4 1.
By considering Vertex Exponents equation .
we show that for each i = 1, 2, .
, n there is a walk from v1 to vi with [ ] [ 3 .
Oe n2 Oe n .
/8 .
3 Oe 3n2 Oe n .
/8 Let p1,i be a path from v1 to vi , i = 1, 2, .
, n.
Notice that since M is an invertible matrix, the system
[ ] [
] [ 3
1i ) .
Oe n2 Oe n .
/8 M 1
1i ) .
3 Oe 3n2 Oe n .
/8 has solution the integer vector
] [
Oe .
/4 .
1i )/2 Oe .
Oe .
1i )/2 .
Oe .
/2 .
Oe .
1i )/2 Oe .
Oe .
1i )/2 If i = 1, we can choose r.
1,1 ) = b.
1,1 ) = 0 and hence we have that x1 = .
2 Oe 2n Oe .
/4 > 0 and x2 = .
Oe .
/2 > 0.
If i = n, then using the .
, .
-path we have x1 = .
Oe .
/4 .
/2 Ou 0 and x2 = 0.
If i = .
Oe .
/2, then using the (.
/2,.
-path v1 Ie vn Ie vnOe1 Ie A A A Ie v.
Oe.
/2 we have x1 = 0 and x2 = .
Oe .
/4.
Notice that for each vertex vi , i = n, .
Oe .
/2, there exists a path p1i from v1 to vi with 0 O r.
1i ) O .
Oe .
/2 and 0 O b.
1i ) O .
Oe .
/2.
More over if b.
1i ) Ou 1, then either r.
1i ) = .
Oe.
/2 or r.
1i ) = 1.
These facts imply that x1 > 0 and x2 > 0.
Hence we now conclude that the system .
has a nonnegative integer solution.
Proposition 3.
3 implies that L.
1 ) O .
3 Oe 2n2 Oe n .
/4 1.
Combining this with .
we have L.
1 ) = .
3 Oe 2n2 Oe n .
/4 1.
Since for every k = 2, 3, .
, n we have d.
k , v1 ) = k Oe 1.
Proposition 3.
4 implies that L.
k ) O .
3 Oe 2n2 Oe n .
/4 k.
for all k = 1, 2, .
, n.
Now using .
we conclude that L.
k ) = .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, n.
Lemma 4.
For the two-colored digraph Ln of type II we have L.
k ) = .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, n.
Proof.
We Arst show that L.
k ) Ou .
3 Oe 2n2 Oe 3n .
/4 k for all k = .
1, 2, .
, n.
Since the red path of length .
/2 in Ln is the path v.
Oe.
/2 Ie v.
Oe.
/2 Ie A A A Ie v1 Ie vn Ie vnOe1 , we set xO = v.
Oe.
/2 and y O = vnOe1 .
We split the proof into three cases.
Case 1: 1 O k O .
Oe .
/2 Taking y O = vnOe1 , then there is a unique path pk,nOe1 from vk to vnOe1 .
This path is a .
1, .
-path.
Using this path and the deAnition of u0 in equation .
we have u0 = .
Oe .
/2 .
Syahmarani and Suwilo Taking xO = v.
Oe.
/2 , there are two paths pk,.
Oe.
/2 from vk to v.
Oe.
/2 .
They are a .
, .
Oe .
-path and a .
1, .
Oe .
-path.
Using the .
, .
Oe .
path and the deAnition of v0 in equation .
we have v0 = .
Oe .
Oe 1 Oe 2.
/4.
Using the .
1, .
Oe .
-path and the deAnition of v0 in equation .
we have v0 = .
Oe .
Oe 1 Oe 2.
/4 1.
Hence, we conclude that v0 = .
Oe .
Oe 1 Oe 2.
/4.
By Theorem 3.
2, equations .
we conclude that [ ] ] [ 3 Oe .
/2 .
Oe n2 Oe 5n .
/8 k OuM Oe .
Oe 1 Oe 2.
/4 .
3 Oe 3n2 Oe n .
/8 .
From .
we conclude that s t = L.
k ) Ou .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, .
Oe .
/2.
Case 2: .
/2 O k O n Oe 1 Taking y O = vnOe1 , there is a unique path pk,nOe1 from vk to vnOe1 which is a (.
/2, k Oe .
Oe .
-path.
Using this path and the deAnition of u0 in equation .
we have u0 = .
2 Oe .
/2 Oe k.
/2.
Taking xO = v.
Oe.
/2 , there is a unique path pk,.
Oe.
/2 from vk to v.
Oe.
/2 .
This path is a .
, k Oe .
Oe .
-path.
Using this path and the deAnition of v0 in equation .
, we have v0 = k.
Oe .
/2 Oe .
Oe .
2 /4.
Equations .
, .
and Theorem 3.
2 imply that L.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
3 Oe 2n2 Oe 3n .
/4 k for all k = .
/2, .
/2, .
, n Oe 1.
Case 3: k = n There is a .
, .
-path pk,nOe1 from vk to vnOe1 .
Using this path and the deAnition of u0 in equation .
we have u0 = .
Oe .
/2.
There is a .
, .
Oe .
-path pk,.
Oe.
/2 from vk to v.
Oe.
/2 .
Using this path and the deAnition of v0 in equation .
we And that v0 = .
Oe .
2 /4 Oe .
Oe .
/2.
Theorem 3.
2 implies that L.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
3 Oe 2n2 Oe 3n .
/4 n = .
3 Oe 2n2 Oe 3n .
/4 k for k = n.
Now from .
, .
, and .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, n.
Vertex Exponents We next show the upper bound, that is L.
k ) O .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, n.
We Arst show that L.
1 ) = .
3 Oe 2n2 Oe 3n .
/4 1 and then we use Proposition 3.
4 in order to determine the upper bound for exponents of other vertices.
From .
it is known that L.
1 ) Ou .
3 Oe 2n2 Oe 3n .
/4 1.
Thus, it remains to show that L.
1 ) O .
3 Oe 2n2 Oe 3n .
/4 1.
By considering .
we show that for each i = 1, 2, .
, n there is a walk from v1 to vi consisting of .
3 Oe n2 Oe 5n .
/8 red arcs and .
3 Oe 3n2 Oe n .
/8 blue arcs.
Let p1i be a path form v1 to vi , i = 1, 2, .
, n.
Notice that the system
[ ] [
] [ 3
1i ) .
Oe n2 Oe 5n .
/8 M 1
1i ) .
3 Oe 3n2 Oe n .
/8 has integer solution ] [ b.
1,i ) .
1,i ) Oe r.
1,i )).
Oe .
/2 .
Oe .
Oe 3 2r.
1,i )]/4 Oe b.
1,i ).
Oe .
/2 If i = 1, we choose r.
1,1 ) = b.
1,1 ) = 0.
This implies x1 = n Oe 1 > 0 and x2 = .
Oe .
2 /4 > 0.
Since for every i = 2, 3 .
, n there is a path p1i from v1 to vi with b.
1i ) Oe r.
1i ) Ou Oe1, we have x1 = b.
1,i ) .
1,i ) Oe r.
1,i )].
Oe .
/2 Ou 0.
Notice also that for any i = 2, 3, .
, n there is a path p1i from v1 to vi with b.
1i ) O .
Oe .
/2 and every such path p1i has r.
1i ) Ou 1.
Hence x2 = .
Oe .
Oe 3 2r.
1,i )]/4 Oe b.
1,i ).
Oe .
/2 Ou 0.
Therefore the system .
has a nonnegative integer solution.
Since v1 lies on both cycles.
Proposition 3.
3 implies that L.
1 ) O .
3 Oe 2n2 Oe 3n .
/4 1.
Now combining .
we And that L.
1 ) = .
3 Oe 2n2 Oe 3n .
/4 1.
Since for any k = 1, 2, .
, n we have d.
k , v1 ) = k Oe 1, by Proposition 3.
4 we have L.
k ) O .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, n.
Finally, combining .
we conclude that L.
k ) = .
3 Oe 2n2 Oe 3n .
/4 k for all k = 1, 2, .
, n.
Lemma 4.
For the two-colored digraph Ln .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, n.
of type i we have L.
k ) = Proof.
We Arst show that L.
k ) Ou .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, n.
Since the red path of length .
/2 is the path v.
/2 Ie v.
Oe.
/2 Ie A A A Ie v1 Ie vn , we set xO = v.
/2 and y O = vn .
We split the proof into two cases.
Case 1: 1 O k O .
/2 Considering the .
, .
-path from vk to vn and the deAnition of u0 in equation .
we have u0 = k.
Oe .
/2.
Syahmarani and Suwilo We note that there are two paths from vk to v.
/2 .
They are a .
Oe 1, .
Oe .
-path and a .
, .
Oe .
-path.
Using the .
Oe 1, .
Oe .
-path and the deAnition of v0 in equation .
we have that v0 = .
Oe .
Oe 2k .
/4.
Using the .
, .
Oe .
-path and the deAnition of v0 in equation .
we have v0 = .
Oe .
Oe 2k .
/4 1.
Hence, we conclude that v0 = .
Oe .
Oe 2k .
/4.
Now by considering Theorem 3.
2, equation .
and equation .
we have [ ] ] [ 3 Oe .
/2 .
Oe n2 Oe 5n Oe .
/8 k OuM Oe .
Oe 2k .
/4 .
3 Oe 3n2 Oe n .
/8 .
Thus from .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, .
/2.
Case 2: .
/2 O k O n Considering the (.
/2, k Oe.
-path from vk to vn and the deAnition of u0 in equation .
we have u0 = .
Oe .
/2.
Considering the .
, k Oe .
path from vk to v.
/2 and the deAnition of v0 in equation .
we have v0 = .
Oe .
k Oe n Oe .
/4.
By Theorem 3.
2, we have L.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
2 Oe 2n2 Oe 3.
/4 k for all k = .
/2, .
/2, .
, n.
Now from .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, n.
We next show that L.
k ) O .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, n.
For this purpose we Arst show that L.
1 ) = .
3 Oe2n2 Oe3.
/4 1 and then we use Proposition 3.
4 in order to get the upper bounds for L.
k ) for k = 2, 3, .
, n.
From .
it is inferred that L.
1 ) Ou .
3 Oe 2n2 Oe 3.
/4 1.
It remains to show that L.
1 ) O .
3 Oe 2n2 Oe 3.
/4 1.
By considering .
we show that for each vertex vi , i = 1, 2, .
, n, there is a walk from v1 to vi consisting of .
3 Oen2 Oe5n .
/8 red arcs and .
3 Oe3n2 Oen .
/8 blue arcs.
For i = 1, 2, .
, n let p1,i be a path from v1 to vi .
Consider the system of equations [ ] [ ] [ 3 1,i ) .
Oe n2 Oe 5n .
/8 .
1,i ) .
3 Oe 3n2 Oe n .
/8 The solution to the system .
is the integer vector
] [
1,i ) .
1,i ) Oe r.
1,i )).
Oe .
/2 .
Oe .
Oe .
/4 r.
1,i ).
Oe .
/2 Oe b.
1,i ).
Oe .
/2 Vertex Exponents If i = 1, we can choose r.
1,1 ) = b.
1,1 ) = 0.
This implies x1 = .
Oe .
/2 > 0 and x2 = .
2 Oe 4n .
/4 > 0.
Notice that for each i = 2, 3, .
, n there is a path p1i from v1 to vi with b.
1i ) O .
Oe .
/2.
Hence, x2 Ou 0.
Moreover, there is a path from v1 to vi with 1 b.
1i ) Oe r.
i1 ) Ou 0.
Hence we have x1 Ou 0.
These imply that the system .
has a nonnegative integer solution.
Since the vertex v1 lies on both cycles, by Proposition 3.
3 we conclude that L.
1 ) O .
3 Oe 2n2 Oe 3.
/4 1.
Since for each vertex vk , k = 2, 3, .
, n, d.
k , v1 ) = k Oe1.
Proposition 3.
4 guarantees that L.
k ) O .
3 Oe 2n2 Oe 3.
/4 k for all k = 1, 2, .
, n.
Now combining .
we conclude that L.
k ) = .
3 Oe2n2 Oe3.
/4 k for all k = 1, 2, .
, n.
Lemma 4.
For the two-colored digraph Ln of type IV we have L.
k ) = .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, n.
Proof.
Since the red path of length .
/2 is the path vnOe1 Ie vnOe2 Ie A A A Ie v.
Oe.
/2 , we set xO = vnOe1 and y O = v.
Oe.
/2 .
We split the proof into three cases depending on the position of vk .
Case 1 : 1 O k O .
Oe .
/2 There are two paths from vk to v.
Oe.
/2 .
They are a (.
Oe .
/2, .
-path and a (.
/2, k .
-path.
Using the (.
Oe .
/2, .
-path we And from the deAnition of u0 in equation .
that u0 = .
Oe.
2 /4Oek.
/2.
Using the (.
/2, k .
-path we And from the deAnition of u0 in equation .
that u0 = .
Oe.
2 /4Oek.
/2Oe1.
Hence we choose u0 = .
Oe .
2 /4 Oe k.
/2 Oe 1 = .
2 Oe .
/4 Oe .
/2.
We note that there is a unique path pk,nOe1 from vk to vnOe1 which is a .
, k .
Using this path we And from the deAnition of v0 in equation .
that v0 = .
Oe .
/2 Theorem 3.
2, equation .
and equation .
imply that [ ] ] [ 3 Oe n2 Oe n .
/8 OuM 3 Oe 3n2 Oe n .
/8 k From .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, .
Oe .
/2.
Case 2 : .
Oe .
/2 O k O n Oe 1 There is a unique pk,.
Oe.
/2 -path from vk to v.
Oe.
/2 which is a .
Oe .
Oe .
/2, .
Using this path, from the deAnition of u0 in equation .
we And that u0 = k.
Oe .
/2 Oe .
Oe .
Oe .
/4.
There is a unique path pk,nOe1 from vk to vnOe1 Syahmarani and Suwilo which is a .
Oe .
Oe .
/2, .
Oe .
-path.
Using this path, from the deAnition of v0 in equation .
we And that v0 = .
Oe .
2 /4 .
Oe .
2 /4 Oe k.
Oe .
/2.
Theorem 3.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
Oe .
Oe .
/2 Oe .
Oe .
Oe .
Oe .
2 /4 .
Oe .
2 /4 Oe k.
Oe .
= .
3 Oe 2n2 Oe n .
/4 k for all k = .
Oe .
/2, .
/2, .
, n Oe 1.
Case 3: k = n There is a unique path from vk to v.
Oe.
/2 which is a (.
/2, .
-path.
Using this path we And from the deAnition of u0 in equation .
that u0 = .
2 Oe.
/4Oe.
/2.
There is a unique path pk,nOe1 from vk to vnOe1 which is a .
, .
-path.
Using this path we And from the deAnition of v0 in equation .
that v0 = .
Oe .
/2.
Theorem 3.
[ ]
] [ 3
Oe n2 Oe n .
/8 OuM .
3 Oe 3n2 Oe n .
/8 and hence L.
k ) Ou .
3 Oe 2n2 Oe 5n .
/4 n.
We note that for the .
, .
-path from vn to vnOe1 , the system
[ ] [ ] [ 3
Oe n2 Oe n .
/8 M 1 .
3 Oe 3n2 Oe n .
/8 has nonnegative integer solution x1 = .
2 Oe .
/4 x2 = 0.
This implies [ and ] there .
3 Oe n2 Oe n .
/8 is no walk from vn to vnOe1 with composition Hence .
3 Oe 3n2 Oe n .
/8 L.
n ) > .
3 Oe 2n2 Oe 5n .
/4 n.
Notice that the shortest walk from vn to vnOe1 with at least .
3 Oe n2 Oe n .
/8 red arcs and .
3 Oe 3n2 Oe n .
/8 blue arcs is the walk that starts at vn , moves to vnOe2 and then moves .
2 Oe .
/4 times around the cycle back at vnOe.
Anally moves to vnOe1 .
The composition of [ 3C1 and .
Oe n2 3n .
/8 this walk is Thus we now have .
3 Oe 3n2 3n .
/8 L.
n ) Ou .
3 Oe 2n2 3n .
/4 = .
3 Oe 2n2 Oe n .
/4 n.
From .
, .
we conclude that L.
k ) Ou .
3 Oe 2n2 Oe n .
/4 k for all k = 1, 2, .
, n.
We next show L.
k ) O .
3 Oe 2n2 Oe n .
k by Arst showing that L.
1 ) = .
3 Oe 2n2 Oe n .
/4 1, and then use Proposition 3.
4 to get upper bound for exponent of the vertex vk , k = 2, 3, .
, n.
From .
we know that for k = 1.
1 ) Ou .
3 Oe 2n2 Oe n .
/4 1 and from .
we know that this bound Vertex Exponents .
3 Oe n2 Oe n .
/8 It remains to .
3 Oe 3n2 Oe n .
/8 show that L.
1 ) O .
3 Oe 2n2 Oe n .
/4 1.
For each i = 1, 2, .
, k we show that there is an .
, .
-walk w1,i from v1 to vi with composition ] [ 3 r.
1,i ) .
Oe n2 Oe n .
/8 b.
1,i ) .
3 Oe 3n2 Oe n .
/8 is obtained by walks with composition For any vertex vi , i = 1, 2, 3, .
, n let p1i be a path from v1 to vi .
The system
[ ] [
] [ 3
1i ) .
Oe n2 Oe n .
/8 .
1i ) .
3 Oe 3n2 Oe n .
/8 has integer solution ] [ r.
1,i ) (.
Oe .
/2 b.
1,i ) Oe r.
1,i )).
/2 .
Oe b.
1,i )).
Oe .
/2 r.
1,i ).
Oe .
/2 If i = 1, we can choose r.
1,1 ) = b.
1,1 ) = 0.
This implies x1 = .
2 Oe 4n Oe .
/4 > 0 and x2 = nOe1 > 0.
We note that for any vertex vi , i = 2, 3, .
, n there is a path p1i from v1 to vi with 2 O b.
1i ) O .
Oe .
/2.
Moreover, if 3 O b.
1i ) O .
Oe .
/2, then r.
1i ) = .
Oe .
/2.
Hence x2 Ou 0.
Notice also that for any vertex vi , i = 2, 3, .
, n we can And a path p1i with b.
1i ) Oe r.
1i ) Ou Oe.
Oe .
/2.
Hence x1 Ou 0.
Hence the system .
has a nonnegative integer solution.
Since the vertex v1 lies on both cycles.
Proposition 3.
3 guarantees that L.
1 ) O .
3 Oe 2n2 Oe n .
/4 1.
considering equation .
we conclude that L.
1 ) = .
3 Oe 2n2 Oe n .
/4 1.
Since for each k = 2, 3, .
, n we have d.
k , v1 ) = k Oe 1.
Proposition 3.
4 implies L.
k ) O .
3 Oe 2n2 Oe n .
/4 k for k = 1, 2, .
, n.
Combining .
we conclude that .
k ) = .
3 Oe 2n2 Oe n .
k for all k = 1, 2, .
, n.
Theorem 4.
Let Ln be a primitive two-colored digraph on n Ou 5 vertices whose underlying digraph is the digraph Ln in Figure 1.
If exp(Ln ) = .
3 Oe 2n2 .
/2, then .
Oe 2n Oe 3n .
/4 O L.
k ) O .
Oe 2n 3n .
/4 for all k = 1, 2, .
, n Proof.
By Lemma 4.
1 through Lemma 4.
4 for each k = 1, 2, .
, n we have that .
3 Oe 2n2 Oe 3.
/4 k O L.
k ) O .
3 Oe 2n2 Oe n .
/4 k.
This implies for any k = 1, 2, .
, n we have .
3 Oe 2n2 Oe 3n .
/4 O L.
k ) O .
3 Oe 2n2 3n .
/4.
We now discuss vertex exponents for the two-colored digraphs Ln exponents is 2n2 Oe 6n 2.
Theorem 4.
Let Ln be a primitive two-colored digraph on n Ou 5 vertices whose underlying digraph is the digraph Ln in Figure 1.
If exp(Ln ) = 2n2 Oe 6n 2, then for any vertex vk , k = 1, 2, .
, n we have .
Oe 4n .
O L.
k ) O .
2 Oe 2n Oe .
Syahmarani and Suwilo Proof.
Since exp(Ln ) = 2n2 Oe6n 2.
Corollary 2.
4 implies that Ln has a unique .
, .
-path that lies on both cycles.
This implies the .
, .
-path of Ln is of the form a Ie aOe1 Ie aOe2 for some 3 O a O nOe2.
We show that L.
k ) = n2 Oe3n k 2Oea for all k = 1, 2, .
, n.
We Arst show that D.
k ) Ou n2 Oe 3n k 2 Oe a for all k = 1, 2, .
, n.
We use path from vk to vaOe2 to determine the value of the quantity u0 in equation .
and we use path from vk to va to determine the value of the quantity v0 in equation .
We split the proof into three cases depending on the position of the vertex vk .
Case 1 : 1 O k O a Oe 2 We note that there are two paths from vk to vaOe2 .
They are a (.
Oe .
/2 Oe UO.
Oe 2 Oe .
/2UU, .
Oe.
/2OeUO.
Oe2Oe.
/2UO)-path and a (.
/2OeUO.
Oe2Oe.
/2UU, .
Oe.
/2Oe UO.
Oe 2 Oe .
/2UO)-path.
Using UO aOe2Oek UO Arst UO and UUthe deAnition of u0 in equation .
nOe1 aOe2Oek we have u0 = 1 n 1 Oe Using the second path and the UO aOe2Oek UO nOe1 UO aOe2Oek UU deAnition of u0 in equation .
we have u0 = n 1 Oe 2 Hence we conclude that u0 = .
UO.
Oe 2 Oe .
/2UO/2 Oe .
Oe .
UO.
Oe 2 Oe .
/2UU/2.
There are two paths from vk to va .
They are a (.
Oe.
/2OeUO.
Oe2Oe.
/2UU, .
Oe .
/2OeUO.
Oe2Oe.
UO)-path and a (.
Oe.
/2OeUO.
Oe2Oe.
/2UU, .
Oe.
/2OeUO.
Oe2Oe.
UO)path.
Using UOthe Arst UO path UO the UUdeAnition of v0 in equation .
we have v0 = nOe1 aOe2Oek nOe3 aOe2Oek nOe3Oe 2 Using the second path and the deAnition of UO aOe2Oek UO nOe3 UO aOe2Oek UU v0 in equation .
we have v0 = n Oe 2 Oe nOe1 Hence we conclude that v0 = n Oe 3 Oe .
Oe .
UO.
Oe 2 Oe .
/2UO/2 .
Oe .
UO.
Oe 2 Oe .
/2UU.
Now Theorem 3.
2, equation .
and equation .
imply that [ ] Ou
[ ]
M 0
UO nOe1 UO aOe2Oek UU n 1 aOe2Oek Oe .
/2 .
/2 Oe UO2 aOe2Oek aOe2Oek Oe .
/2 .
Oe .
/2 n Oe 3 Oe nOe1
nOe3
[ 2
Oe 2n Oe .
/2 Oe UO.
Oe k Oe .
/2UU .
3 Oe 4n .
/2 Oe UO.
Oe 2 Oe .
/2UO Hence we now have D.
k ) Ou n2 Oe 3n Oe (UO.
Oe 2 Oe .
/2UU UO.
Oe 2 Oe .
/2UO) = n2 Oe 3n k 2 Oe a .
for k = 1, 2, .
, a Oe 2.
Case 2 : k = a Oe 1, a There is a unique path from vk to vaOe2 and it is a .
Oe a 2, .
-path.
Using this path and the deAnition of u0 in equation .
we have that u0 = .
Oe .
Oe a .
/2.
Vertex Exponents There are two paths from vk to va .
They are a .
Oea 2 .
Oe.
/2, .
Oe.
-path and a .
2Oea .
Oe.
/2, .
Oe.
-path.
Using the Arst path and the deAnition of v0 in equation .
we have that v0 = nOe3Oe.
Oe.
2Oe.
/2.
Using the second path and the deAnition of v0 in equation .
we have that v0 = nOe2Oe.
Oe.
2Oe.
/2.
Hence we conclude that v0 = n Oe 2 Oe .
Oe .
2 Oe .
/2.
Now Theorem 3.
2, equation .
and equation .
imply that D.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 = .
Oe .
Oe .
Oe a .
/2 n[.
Oe .
Oe .
Oe .
Oe a .
= n2 Oe 3n k 2 Oe a .
for all k = a Oe 1, a.
Case 3 : a 1 O k O n There is a unique path from vk to vaOe2 which is (UO.
Oe .
/2UU 2.
UO.
Oe .
/2UO)path.
UsingUU thi.
path and UO the UO deAnition of u0 in equation .
we have u0 = ( nOe1 ) (UO kOea n 1 kOea Oe There is a unique path from vk to va which is a (UO.
Oe .
/2UU.
UO.
Oe .
/2UO)-path.
UO Using UU this UO UO the deAnition of v0 in equanOe1 kOea nOe3 kOea tion .
we have that v0 = 2 Oe 2 By Theorem 3.
2 we have L.
k ) Ou Ee(C1 )u0 Ee(C2 )v0 (UO UU
UO)
nOe1 kOea n 1 kOea = .
Oe .
2 Oe
UO)
nOe1 kOea n 1 kOea Oe Hence = n3 Oe 3n 2 UO.
Oe .
/2UU UO.
Oe .
/2UO = n2 Oe 3n k 2 Oe a .
for a 1 O k O n.
From equation .
, equation .
and equation .
we conclude that L.
k ) Ou n3 Oe 3n k 2 Oe a .
for all k = 1, 2, .
, n.
We now show that L.
k ) O n3 Oe 3n k 2 Oe a for k = 1, 2, .
, n.
Arst show that L.
1 ) O n3 Oe 3n 3 Oe a and then we use Proposition 3.
4 to show that L.
O n2 Oe 3n k 2 Oe a for k = 2, 3, .
, n.
By considering equation .
it suEces to show that for each vertex vi , i = 1, 2, .
, n there is a walk w1,i from v1 to vi with composition ] [ 2 r.
1,i ) .
Oe 2n Oe .
/2 Oe UO.
Oe .
/2UU .
1,i ) .
3 Oe 4n .
/2 Oe UO.
Oe .
/2UO Syahmarani and Suwilo For each i = 1, 2, .
, n, let p1,i be a path from v1 to vi .
We note that the solution to the system
[ ] [
] [ 2
1,i ) .
Oe 2n Oe .
/2 Oe UO.
Oe .
/2UU .
1,i ) .
3 Oe 4n .
/2 Oe UO.
Oe .
/2UO is the integer vector
[ ]
UO.
Oe .
/2UO.
/2 Oe UO.
Oe .
/2UU.
Oe .
/2 n Oe 3 UO.
Oe .
/2UU.
Oe .
/2 Oe UO.
Oe .
/2UO.
Oe .
/2 b.
1,i ) .
1,i ) Oe r.
1,i )).
Oe .
/2 .
1,i ) Oe b.
1,i )).
Oe .
/2 Oe b.
1,i ) .
We show that x1 Ou 0 and x2 Ou 0.
We consider two cases when a is even and a is If a is even, then UO.
Oe .
/2UO = .
Oe .
/2 and UO.
Oe .
/2UU = .
Oe .
/2.
This [ ] [ .
Oe .
/2 .
Oe .
/2 b.
1,i ) Oe .
1,i ) Oe b.
1,i )].
Oe .
/2 .
Oe a Oe .
/2 .
1,i ) Oe b.
1,i )].
Oe .
/2 Oe b.
1,i ) Since a is even, we have that 0 O r.
1,i ) Oe b.
1,i ) O 2.
If r.
1,i ) Oe b.
1,i ) = 0, then b.
1,i ) O .
Oe 1 Oe .
/2.
This implies x1 > 0 and x2 Ou 0.
If r.
1,i ) Oe b.
1,i ) = 1, there is a path p1,i with b.
1,i ) O .
Oe .
/2.
This implies x1 > 0 and x2 > 0.
1,i ) Oe b.
1,i ) = 2, then b.
1,i ) Ou .
1 Oe .
/2.
This implies x1 Ou 0 and x2 > 0.
Therefore for each vertex vi , i = 1, 2, .
, n, there is a path p1,i from v1 to vi such that the system .
has nonnegative integer solution x1 Ou 0 and x2 Ou 0.
If a is odd, then UO.
Oe .
/2UO = UO.
Oe .
/2UU = .
Oe .
/2.
This implies [ ] [ .
Oe .
/2 b.
1,i ) Oe .
1,i ) Oe b.
1,i )].
Oe .
/2 n Oe 3 Oe .
Oe .
/2 .
1,i ) Oe b.
1,i )].
Oe .
/2 Oe b.
1,i ) Since a is odd, for each vertex vi , i = 1, 2, .
, n there is a path p1,i with Oe1 O r.
1,i ) Oe b.
1,i ) O 1.
If r.
1,i ) Oe b.
1,i ) = Oe1, there is a path p1,i with b.
1,i ) O .
Oe .
/2.
This implies x1 > 0 and x2 Ou 0.
If r.
1,i ) Oe b.
1,i ) = 0, there is a path p1,i with b.
1,i ) O .
Oe .
/2.
This implies x1 > 0 and x2 > 0.
Finally if r.
1,i ) Oe b.
1,i ) = 1, there is a path p1,i with b.
1,i ) Ou .
Oe a .
/2.
This implies x1 Ou 0 and x2 > 0.
Therefore for each vertex vi , i = 1, 2, .
, n, there is a path p1,i from v1 to vi such that the system .
has nonnegative integer solution x1 Ou 0 and x2 Ou 0.
Since the system .
has a nonnegative integer solution and the vertex v1 belongs to both cycles.
Proposition 3.
3 guarantees that L.
1 ) O n2 Oe 3n 3 Oe a.
Combining this with equation .
we conclude that L.
1 ) = n2 Oe 3n 3 Oe a.
Since for k = 2, 3, .
, n we have d.
k , d1 ) = k Oe 1.
Proposition 3.
4 implies that L.
k ) O n2 Oe 3n k 2 Oe a .
for k = 1, 2, .
, n.
Finally combining equation .
and equation .
we conclude that L.
k ) = n2 Oe 3n k 2 Oe a for k = 1, 2, .
, n.
We note that 3 O a O n Oe 2.
This implies Vertex Exponents n2 Oe 4n 4 k O L.
k ) O n2 Oe 3n k Oe 1.
Therefore for any k = 1, 2, .
, n we have n2 Oe 4n 5 O L.
k ) O n2 Oe 2n Oe 1.
References