1. Introduction
This paper considers only finite undirected simple graphs. Let G be a graph with order n, its the adjacency matrix is defined as follows:
Obviously,
is a real symmetric matrix in which all diagonal elements are 0 and all other elements are 0 or 1, its eigenvalues are all real numbers. The n eigenvalues of
are said to be the eigenvalues of the graph G and to form the spectrum of this graph. The number of nonzero and the number of zero eigenvalues in the spectrum of G are called rank and nullity of the graph G, and are denoted by
and
respectively. Obviously
. There have been diverse studies on the nullity of a graph [1] - [12], it is related to the stability of molecular represented by the graph. However, there is very little literature on the rank of a graph. It is known that
if and only if G is an empty graph without edges. Obviously, there is no graph G where
. In [1] [13], graph G is characterized where
. In [2] [14], graph G is characterized where
. In [15], graph G is characterized where
. In this paper, by using the operation of multiplication of vertices, a characterization for graph G with pendant vertices and
is shown, and then a characterization for graph G with pendant vertices and
less than or equal to 7 is shown.
This paper is organized as follows: In Section 2, some necessary lemmas are given, in Section 3, a characterization for graph G with pendant vertices and
is shown, and then a characterization for graph G with pendant vertices and
is shown.
Let G be a graph, for a vertex
, define
to be the neighborhood of vertex x in G. A vertex subset
of a graph G is an independent set of G if
, the subgraph induced by I, is edgeless. Now let us introduce a graph operation. Let
, and
be a vector of positive integers. Denote by
the graph obtained from G by replacing each vertex
of G with an independent set of
vertices
and joining
with
if and only if
and
are adjacent in G. The resulting graph
is said to be obtained from G by multiplication of vertices. Let
be the set of some graphs, we denote by
class of all graphs that can be constructed from one of the graphs in
by multiplication of vertices.
denotes the complete graph on n vertices. Undefined concepts and notations will follow [16].
2. Some Lemmas
Lemma 2.1. [1]
1) Let
and
be two graphs, if
, then
.
2) Let H be a vertex-induced subgraph of G, then
.
Lemma 2.2. [14] Let G and H be two graphs, if
, then
.
Lemma 2.2 indicates that multiplication of vertices does not change the rank of the graph. A graph is called a basic graph if it has no isolated vertices and can not be obtained from other graphs by multiplication of vertices. Otherwise, it is not a basic graph. Hence, a graph with no isolated vertices is not a basic graph if and only if it has two vertices which have the same neighborhoods. According to the lemma 2.2, to characterize a graph of rank k, we only need to characterize all the basic graphs of rank k. In [1] [13], they characterized that the connected basic graph of rank 2 is
and the connected basic graph of rank 3 is
. For convenience, let’s say
,
; In [2] [14], they characterized all connected basic graphs of rank 4 (as shown in Figure 1).
Lemma 2.3. [14] Let G be a graph without isolated vertices, then
if and only if
, where
, every
is shown in Figure 1.
Lemma 2.4. [15] Let G be a graph without isolated vertices, then
if and only if
, where
, every
is shown in Figure 2 and Figure 3.
Lemma 2.5. [12] Let G be a graph with a pendant vertex, and let H be the induced subgraph of G obtained by deleting the pendant vertex together with the vertex adjacent to it. Then
, equivalently
.
3. Main Conclusions
Let H be a graph with
, and
is a vector with
or 2, (
). Then
can be divided into two sets:
and
. Let
and
be the vertices in
by multiplying the vertex
in H when
. For a subset
, we construct a graph
as follows:
Figure 2. The graphs with exactly 5 vertices and rank 5.
Figure 3. The basic graphs with more than 5 vertices and rank 5.
By the definition,
has a pendant vertex x.
Lemma 3.1. If H is a basic graph, then
is also a basic graph.
Proof. For any
, if
, as H is a basic graph, then
. by the definition of the graph
, we have
or
, either way, we have
(
,
). If
and
, by the construction of the graph
, we have
and
;
and
for all
;
and
for all
(because H has no isolated vertices). In a word, any two vertices in
don’t have the same neighborhoods. Therefore,
is a basic graph.
For the convenience of drawing, when
, we use a hollow circle to indicate two vertices
and
, which have the same neighborhoods in
, the vertex y is adjacent to
but not adjacent to
, and we use a black dot to indicate exactly one vertex. For example, the graph
is depicted in Figure 4, where
,
,
and
.
Since there are multiple choices for the vector m and the subset U, there are also multiple choices for the graph
, represented by
as the set of all graphs
.
Theorem 1. Let G be a graph without isolated vertices but with pendant vertices,
Figure 4. The graph
where
.
if and only if
, where
,
is the same thing as Lemma 2.4.
Proof. Without loss of generality, we assume that G is a basic graph. Let H be the induced subgraph of G obtained by deleting the pendant vertex x together with the vertex y adjacent to it. By Lemma 2.5, we have
. Furthermore, H does not have isolated vertices (if not, then the G contains at least an isolated vertex or two pendant vertices all adjacent to y, so G is not a connected graph, or G is not a basic graph, which is a contradiction). Then by Lemma 2.4,
. Let
, where
is a vector of positive integers, and
. If
, then there exists
such that
(since
or
). If
,
and
are all adjacent to y or none are adjacent to y, then
, However, G is a basic graph, this is a contradiction. So
, one and only one of the two vertices
and
is adjacent to y when
. Therefore, we conclude that
.
A graph G is called a basic extremal graph of rank k. Let it be a basic graph of rank k, and it is not a proper vertex-induced subgraph of any basic graphs of rank k. When we study the graph of rank k, we just need to find out the basic extremal graph of rank k. Obviously,
is a basic extremal graph of rank 2, let’s say
.
is a basic extremal graph of rank 3, let’s say
.
and
(as shown in Figure 1) are basic extremal graphs of rank 4, let’s say
.
,
,
,
,
,
,
and
(as shown in Figure 2) are basic extremal graphs of rank 5, let’s say
Obviously, in
, every graph is the vertex-induced subgraph of a certain graph in
.
Let H be a a basic graph of rank 5, then all graphs in the set
are basic graphs with pendant vertices and
. Let
,
, and every vector
or 2 (
). If some vectors
, then
can’t be a basic extremal graph of rank 7, because it is a proper vertex-induced subgraph of
, where
and
is empty set. Particularly, let’s say
. Easy to prove, if H is a basic extremal graph of rank 5, then
is a basic extremal graph with pendant vertices and
. Hence we have the following theorem.
Theorem 2. Let G be a graph without isolated vertices but with pendant vertices, then
if and only if
, where
is the set of all vertex-induced subgraphs of graphs in set
.
Proof. By
, we know the rank of H is 5. By the definition of
and lemma 2.5, we know its rank is 7. Hence the rank of every graph is less than or equal to 7 in set
. On the contrary, let G be a graph without isolated vertices but with pendant vertices, and
. Similar to the proof of theorem 1,
we have
, where
. Because every graph in
is the vertex-induced subgraph of a certain graph in
, and every graph in
is the vertex-induced subgraph of a certain graph in
. On the other hand, every graph in
is the vertex-induced subgraph of
. So
.
4. Conclusion
By using the operation of multiplication of vertices, a characterization for graph G with pendant vertices and
is shown, and then a characterization for graph G with pendant vertices and
less than or equal to 7 is shown.
Acknowledgements
This work is supported by National Natural Science Foundation of China (11561056, 11661066), Natural Science Foundation of Qinghai Province (2016-ZJ-914).