1. Introduction
In this paper only consider simple graph of finite and unordered.
is a graph,
is vertices set of a graph
, the adjacency matrix
of a graph
is the
symmetric matrix
such that
if
is adjacent to
, and
otherwise. Obviously,
is a real symmetric matrix, and all eigenvalues are real number, denoted by eigenvalues of a graph
. The rank of a graph
, written as
, is defined to be the number of the rank of matrix
. The nullity of a graph
is the multiplicity of the zero eigenvalues of matrix
and denoted by
. Clearly,
. In chemistry, the nullity is correlated with the stability of hydrocarbon that a graph
represented (see [1] - [6] ). Collatz and Sinogowitz [1] posed the problem of characterizing all non- singular graphs, which is required to describe the issue of all nullity greater than zero; although this problem is very hard, still a lot of literature research it (see [5] [7] [8] ). It is known that the rank
of a graph
is equal to 0 if and only if
is a null graph (i.e. a graph without edges), and there is no graph with rank 1. The graph
with the rank
is equal to 2 or 3, which is completely characterized in [8] . The graph
with the rank
is equal to 4, which is completely characterized in [9] . Although in [10] , the graphs with rank 5 are characterized by using forbidden subgraph. In the paper, we completely characterize the graphs with rank no more than 5 by using Matlab. Compared to the method in [10] , the method of this paper is simpler and clearer.
For a vertex
in
, the set of all vertices in
that are adjacent to
is denoted by
. The distance between
and
, denoted by
, is the length of a shortest
,
-path in graph
. The distance between a vertex
and a subgraph
of
, denoted by
, is defined to be the value
. Given a subset
, the subgraph of
induced by
, is written as
. The
-path, the
-cycle and the
- complete graph are denoted by
,
and
, respectively.
A subset
is called an independent set of
if the subgraph
is a null graph. Next we define a graph operation (see page 53 of [6] ). Give a graph
with
. Let
be a vector of positive integers. Denoted by
the graph is obtained from
by replacing each vertex
of
with an independent set of
vertices
and joining
with
if and only if
and
are adjacent in
. The resulting graph
is said to be obtained from
by multi- plication of vertices. For graphs
, we denote by
the class of all graphs that can be obtained from one of the graphs in
by multiplication of vertices.
2. Preliminaries
Lemma 2.1. [9] Suppose that
and
are two graphs. If
, then
.
By Lemma 2.1, we know that the rank of a graph doesn't change by multiplication of vertices. Let
be a graph, if exists a graph
such that
, we call
is a non-basic graph. Otherwise,
is called a basic graph. The following we need find all basic graphs with rank no more than 5.
Lemma 2.2. [3] (1) Let
, where
and
be two graphs. Then
.
(2) Let
be an induced subgraph of
. Then
.
Lemma 2.3. Let
be a connected graph with rank
. Then there exists an induced subgraph
(of
) on
vertices such that
, and
for each vertex
of
.
Proof. Without loss of generality, suppose the previous
row vectors of
are linear independence, and the rest of the row vectors of
are linear combination of the previous
row vectors. Since
is a symmetrical matrix, we know that the rest of the column vectors of
are linear combination of the previous
column vectors. Therefore we can obtain the following matrix by using elementary transformation for
,
where
is the induced subgraph (of
) with the
vertices which is correspondent to the previous
vectors, and
.
Suppose
satisfying
. Then there exists an induced subgraph
of
such that
where
Obviously,
, this con- tradicts to
.
Let
be an induced subgraph of
. For a vertex subset
of
, denote by
(Abbreviated as
) the set
.
3. Main Result
Let
be a graph with
vertices,
be ordered vertices of
.
,
-dimensional column vector
is called adjacency vector of
, where
if
is adjacent to
, and
otherwise.
For obtaining all connected basic graphs with rank
, we have two steps.
Step 1. Find out all graphs with rank
which have exactly
vertices. Denote them by
.
Step 2. Find out all connected graphs with rank
which have more than
vertices. Let
be a graph with rank
. By Lemma 2.3, we know that
contains an induced subgraph
with rank
and
for each vertices
of
. Therefore, we consider the adjacent relation between
and the vertices of
. Let
satisfying
where
is adjacency matrix of
,
,
is a
-dimensional column vector. We calculate all vectors
satisfying condition
by MATLAB.
Obviously,
and adjacency vectors of any vertex
in
satisfy
; this implies that
is not adjacent to
or
. This is not the connected basic graphs that we need to find. Therefore, these
vectors are called trivial vectors and the rest of the vectors (if it is exist) are non- trivial vectors. If there exist non-trivial vectors
such that
holds, then for any vector
, we can obtain a basic graph
on
vertices; its adjacency matrix is
(In fact, suppose
is not a basic graph. Then it is obtained from some graph
by multiplication of vertices. Thus there are two vertices
and
which are not adjacent in
; the adjacent relation between
and any vertex of
and the adjacent relation between
and any vertex of
are the same. Since
is non-trivial vector, we have
. Hence the adjacent relation between
and any vertex of
and the adjacent relation between
and any vertex of
are the same. (where
is the graph obtained from
by removing the vertex
and all edges associated with
). Note
, we have
, a contradiction.)
Repeat the above process for
, it will obtain a family of basic graphs. Continue to repeat the above process for these basic graphs until every basic graph does not produce non-trivial vectors. We can find out all basic graphs with rank
. Now we give two examples.
Example 3.1. Let
be a connected graph and
, then
.
In fact,
is a unique graph [7] with rank 2 which have exactly two xertice. Calculating by MATLAB, have three and only three vectors
and
satisfying that the rank of matrix
is 2, and they are trivial.
Hence,
is unique basic graph with rank 2, thus
.
Example 3.2. Let
be a connected graph and
, then
.
In fact,
is a unique graph [7] with rank 3 which have exactly three vertices. Calculating by MATLAB, have four and only four vectors
and
satisfying that the rank of matrix
is 3, and they are trivial.
Hence,
is unique basic graph with rank 3, thus
.
The paper [9] has given all basic graphs with rank 4 (see Figure 1). It is easy to obtain these graphs with our method. We write the following theorem without proof.
Theorem 3.1. [9] Let
be a graph. Then
if and only if
can be obtained from one of the graphs shown in Figure 1 by multiplication of vertices.
Theorem 3.2. [7] Suppose that
is a graph on 5 vertices. Then
if and only if
is one of the graphs shown in Figure 2.
Figure 2. Graphs have exactly five vertices with rank 5.
Theorem 3.3. Let
be a graph without isolated vertices. Then
if and only if
can be obtained from one of the graphs shown in Figure 2 and Figure 3 by multiplication of vertices.
Proof. We now prove the necessary part. Assume that
is not connected, then
and
,
, where
and
are two graphs. By the example 1 and example 2, we have
. Now assume that
is connected. By Lemma 2.3, there exist induced subgraphs
of
(see Figure 2) such that
for each vertex
of
. According to the differences of induced subgraphs that
contains, we consider the following Case 1-Case 5.
Figure 3. The basic graphs
have more than five vertices with rank 5.
Case 1.
contains an induced subgraph
,
,
The following we first determine basic graph contain
Let
where
,
. For
satisfying
(or
), calculating by MATLAB, we obtain
This implies that not exist non-trivial vectors such that
, hence
is unique basic graph contain
with rank 5, then
.
Case 2.
contains an induced subgraph
,
. Similar with Case 1, we know
.
Case 3.
contains an induced subgraph
,
. Similar with Case 1, we know
.
Case 4.
contains an induced subgraph
,
,
First considering basic graph contain
, let
where
,
. For
satisfying
, calculating by MATLAB, we obtain
we know the first six vectors is trivial.
Case 4.1. For non-trivial vector
, (or
), then there exists a graph
(the adjacency matrix of
is B), it is a basic graph contain
with rank 5.
, Same as above, calculating by MATLAB for
, we obtain 3 non-trivial vectors.
, (or
).
Case 4.1.1. For non-trivial vector
, then there exists a graph
is a basic graph contain
with rank 5. Same as above, calculating by MATLAB for
, we obtain not exist non-trivial vectors. Hence
is a unique basic graph contain
with rank 5.
Case 4.1.2. For non-trivial vector
, then there exists a graph
is a basic graph contain
with rank 5. Same as above, calculating by MATLAB for
, we obtain not exist non-trivial vectors
, the resulting produce a graph
is a basic graph contain
with rank 5. Calculating by MATLAB for
, we obtain not exist non-trivial vectors, Hence
is a unique basic graph contain
with rank 5.
Case 4.1.3. For non-trivial vector
, then there exists a graph
is a basic graph contain
with rank 5. Calculating by MATLAB for
, we obtain exist a non-trivial vectors
. The resulting produce a graph
is a basic graph contain
with rank 5. Similar with Case 4.1.2,
is a unique basic graph contain
with rank 5.
Case 4.2. For non-trivial vector
,(or
), then there exists a graph
is a basic graph contain
with rank 5.
, Same as above, calculating by MATLAB for
, we obtain 3 non-trivial vectors.
, (or
).
Case 4.2.1. For non-trivial vector
, (or
), then there exists a graph
is a basic graph contain
with rank 5. Same as above, calculating by MATLAB for
exist a non-trivial vectors
, the resulting produce a graph
is a basic graph contain
with rank 5. Calculating with MATLAB for
, we obtain not exist non-trivial vectors. Hence
is a unique basic graph contain
with rank 5.
Case 4.2.2. For non-trivial vector
, then there exists a graph
is a basic graph contain
with rank 5. Similar with Case 4.1.1,
is a unique basic graph contain
with rank 5.
Case 4.3. For non-trivial vector
, there exists a graph
is a basic graph contain
with rank 5. Same as above, calculating by MATLAB for
, we obtain three non-trivial vectors
, (or
).
Case 4.3.1. For non-trivial vector
, there exists a graph
is a basic graph contain
with rank 5. Same as above, calculating by MATLAB for
, we obtain not exist non-trivial vectors. Hence
is a unique basic graph contain
with rank 5.
Case 4.3.2. For non-trivial vector
,(or
), there exists a graph
is a basic graph included
with rank 5. Similar with Case 4.1.3, we obtain
and
it is only one basic graph contain
with rank 5.
In a word, basic graph contain
with rank 5 are
,
. Let
be a graph contain
with rank 5, then it must be a multiplication of vertices graph of one of
,
, thus
.
Case 5.
contains an induced subgraph which is
, similar with Case 4, we first find basic graphs contain
with rank 5. The result and logic levels below in Figure 4 and process is omitted.
Figure 4. The level indicate figure of basic graphs contain
with rank 5.
Summarize the previous cases, we can obtain
.
Sufficiency is obvious by the proof process of the necessity. The proof is completed.
By Examples 3.1, 3.2 and Theorems 3.1-3.3, we immediately get the following Theorem
Theorem 3.4. Let
be a graph, then
if and only if
, where
is an induced subgraph of
and
(see Figure 2 and Figure 3).
Acknowledgements
This work is supported by National Natural Science Foundation of China (11561056), National Natural Science Foundation of Qinghai Provence (2016- ZJ-914), and Scientific Research Fund of Qinghai Nationalities University (2015G02).