On the Set of 2 - Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop ()
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 that
is 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
.
Let
Hence
.
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.