ABSTRACT

Let and are positive integers, ,. In this paper we obtain that the set of the 2 − common consequent of primitive digraphs of order with exact vertices having loop is.

1. Introduction

Let be a finite set of order, be a digraph. Elements of are referred as vertices and those of as arcs. The arc of from vertex to vertex is denoted by. Let be a matrix over the Boolean algebra. If the adjacency matrix of, where, if otherwise, then is Boolean matrix. is called adjoint digraph of.

The map: is isomorphism.

Let be a digraph corresponding to the, and

where l > 0 is an integer.

In 1983, Š. Schwarz [1] introduced a concept of the common consequent as follows.

Definition 1.1 Let be a digraph. We say that a pair of vertices, has a common consequent if there is an integer such that

(1)

If have a then the least integer for which (1) holds is denoted by.

Definition 1.2 Let be a digraph. The generalized vertex exponent of, denoted by, is the least integer such that

(2)

In 1996, Bolian Liu [2] extends the common consequent to the common consequent as follows.

Definition 1.3 Let be a digraph. We say that a group of vertices

has a common consequent, if there is an integer such that

(3)

If have a, then the least integer for which (3) holds is denoted by.

If there is at least one group for which

exists, we define

where runs through all groups with elements for which exists. If there is no group for which existswe define. is called of.

A digraph is said to be strongly connected if there exists a path from to for all. A digraph is said to be primitive if there exists a positive integer such that there is a walk of length from to for all. The smallest such is called the primitive exponent of.

A digraph is primitive iff is strongly connected and the greatest common divisor of all cycle lengths of is.

Let and be the set of all primitive digraphs of order with exact vertices having loop. It is obvious that if, then exists for any group

. We define

.

The properties of primitive digraphs and its see [3-5]. In this paper we obtain that the set of the 2 − common consequent of primitive digraphs of order with exact d vertices having loop is

where and are positive integers, , is the least integer greater or equal to a.

2. Preliminaries

It is easy to see that exists by [1].

Lemma 2.1 Let be a primitive digraph of order and be a nonempty proper subset of, then contains at least one element of which is not contained in.

Lemma 2.2 Let be a primitive digraph of order and, where vertex with having a loop, , then.

Proof: Since vertex has a loop, hence, and by lemma 2.1.

The follow lemma is obvious.

Lemma 2.3 [2] If, is a primitive digraph, then.

Lemma 2.4 Let,

where are integers and, then

.

Proof: First of all, It is obvious thatis belong to.

Let, then is a set in which every vertex have a loop, For all.

Case 1.

There exists a walk of length less than or equal to

form to (or from to), and

, then.

Case 2.

There exists a walk of length less than or equal to form to (and form to),

then

.

Case 3.

There exist a walk of length less than or equal to form to, by Lemma 2.2,

hence.

So we have for all.

Note that if, then.

Hence

Let be arbitrary vertex belong to, then there exists a walk of length less than or equal to form

to, then. It is easy to see that if

then.

Hence. The proof is now completed.

3. The Main Results

Theorem 3.1 Let be integers,

then

Proof: Let be set of vertices of and be subset of in which each vertex have a loop,. for all.

Case 1.

There exists a walk of length less than or equal to

form to (or from to), and

, then.

Case 2.

Suppose that there be a walk of length equal to

of, and there be a walk of length equal to of

where.

Let and. If there be one vertex of or belong to, then

.

Otherwise, and

contains at most element of. In other word, contains at least element of. Note that is strongly connected,. There exists a walk of length less than or equal to from to one vertex of

which belong to. Therefore

.

Case 3.

There exist a walk of length less than or equal to form to, by Lamma 2.2

hence.

So we have for all.

Hence

.

Note that

then

.

The proof is completed.

Corollary 3.2 Let and be integers, , then.

Proof: Let be a set of vertices of and let be an arbitrary vertex belong to, then there exists a walk of length from to, where having a loop. Hence

Note that by Lemma 2.4, hence

.

Applying Lemma 2.3, Theorem 2.1 and Theorem 2.2, we have conclusion.

Corollary 3.3 Let and be integers, , then

.

Corollary 3.4 Let be a primitive digraph of order with girth, then

.

Proof: Since is a primitive digraph of order with girth, then is a primitive digraph of order with exact vertices having loop. By Theorem 3.1, we have

.

Theorem 3.5 Let and be integers, , then there exists so that

for arbitrary.

Proof: Let.

We construct so that for arbitrary.

Case 1.

Let

,

. It is obvious that and.

Case 2.

Case 2.1.

LetHence.

Let

obviously,

.

Let, then is the set of vertices which is in cycle lengths of. Let, arbitrary vertex. If, by Lemma 2.4,

.

If, then.

If, then.

Hence.

Case 2.2.

Let, then.

Let

It is obvious that and.

Case 2.3.

Let, then. Let

It is obvious that and.

The proof is now completed.

Remark 3.6 By Theorem 3.5, we obtain that the set of the 2 − common consequent of primitive digraphs of order with exact vertices having loop is

.

But, in Theorem 3.5, is not unique.

Example.

Let

,

.

Obviously,

.but and are not isomorphic digraph.

REFERENCES