A Characterization of Graphs with Rank No More Than 5

DOI: 10.4236/am.2017.81003   PDF   HTML     5,671 Downloads   6,368 Views
The rank of a graph is defined to be the rank of its adjacency matrix. In this paper, the Matlab was used to explore the graphs with rank no more than 5; the performance of the proposed method was compared with former methods, which is simpler and clearer; and the results show that all graphs with rank no more than 5 are characterized.

Keywords

Share and Cite:

Ma, H. and Liu, X. (2017) A Characterization of Graphs with Rank No More Than 5. Applied Mathematics, 8, 26-34. doi: 10.4236/am.2017.81003.

1. Introduction

In this paper only consider simple graph of finite and unordered. $G=\left(V\left(G\right),E\left(G\right)\right)$ is a graph, $V\left(G\right)=\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$ is vertices set of a graph $G$ , the adjacency matrix $A\left(G\right)$ of a graph $G$ is the $n×n$ symmetric matrix $\left[{a}_{ij}\right]$ such that ${a}_{ij}=1$ if ${v}_{i}$ is adjacent to ${v}_{j}$ , and ${a}_{ij}=0$ otherwise. Obviously, $A\left(G\right)$ is a real symmetric matrix, and all eigenvalues are real number, denoted by eigenvalues of a graph $G$ . The rank of a graph $G$ , written as $r\left(G\right)$ , is defined to be the number of the rank of matrix $A\left(G\right)$ . The nullity of a graph $G$ is the multiplicity of the zero eigenvalues of matrix $A\left(G\right)$ and denoted by $\eta \left(G\right)$ . Clearly, $\eta \left(G\right)+r\left(G\right)=|V\left(G\right)|$ . In chemistry, the nullity is correlated with the stability of hydrocarbon that a graph $G$ represented (see  -  ). Collatz and Sinogowitz  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    ). It is known that the rank $r\left(G\right)$ of a graph $G$ is equal to 0 if and only if $G$ is a null graph (i.e. a graph without edges), and there is no graph with rank 1. The graph $G$ with the rank $r\left(G\right)$ is equal to 2 or 3, which is completely characterized in  . The graph $G$ with the rank $r\left(G\right)$ is equal to 4, which is completely characterized in  . Although in  , 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  , the method of this paper is simpler and clearer.

For a vertex $x$ in $G$ , the set of all vertices in $G$ that are adjacent to $x$ is denoted by ${N}_{G}\left(x\right)$ . The distance between $\text{ }u$ and $v$ , denoted by $\text{dist}{\text{ }}_{G}\left(u,v\right)$ , is the length of a shortest $u$ , $v$ -path in graph $G$ . The distance between a vertex $\text{ }u$ and a subgraph $H$ of $G$ , denoted by $\text{dist}{\text{ }}_{G}\left(u,H\right)$ , is defined to be the value $\mathrm{min}\left\{\text{dist}{\text{ }}_{G}\left(u,v\right):v\in V\left(H\right)\right\}$ . Given a subset $S\subseteq V\left(G\right)$ , the subgraph of $G$ induced by $S$ , is written as $G\left[S\right]$ . The $n$ -path, the $n$ -cycle and the $n$ - complete graph are denoted by $\text{ }{P}_{n}$ , ${C}_{n}$ and ${K}_{n}$ , respectively.

A subset $I\subseteq V\left(G\right)$ is called an independent set of $G$ if the subgraph $G\left[I\right]$ is a null graph. Next we define a graph operation (see page 53 of  ). Give a graph $G$ with $V\left(G\right)=\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$ . Let $m=\left({m}_{1},{m}_{2},\cdots ,{m}_{n}\right)$ be a vector of positive integers. Denoted by $G\circ m$ the graph is obtained from $G$ by replacing each vertex ${v}_{i}$ of $G$ with an independent set of ${m}_{i}$ vertices ${v}_{i}^{1},{v}_{i}^{2},\cdots ,{v}_{i}^{{m}_{i}}$ and joining ${v}_{i}^{s}$ with ${v}_{j}^{t}$ if and only if ${v}_{i}$ and ${v}_{j}$ are adjacent in $G$ . The resulting graph $G\circ m$ is said to be obtained from $G$ by multi- plication of vertices. For graphs ${G}_{1},{G}_{2},\cdots ,{G}_{k}$ , we denote by $\mathcal{M}\left({G}_{1},{G}_{2},\cdots ,{G}_{k}\right)$ the class of all graphs that can be obtained from one of the graphs in $\left\{{G}_{1},{G}_{2},\cdots ,{G}_{k}\right\}$ by multiplication of vertices.

2. Preliminaries

Lemma 2.1.  Suppose that $G$ and $H$ are two graphs. If $G\in \mathcal{M}\left(H\right)$ , then $r\left(G\right)=r\left(H\right)$ .

By Lemma 2.1, we know that the rank of a graph doesn't change by multiplication of vertices. Let $G$ be a graph, if exists a graph $H\left(\ncong G\right)$ such that $G\in \mathcal{M}\left(H\right)$ , we call $G$ is a non-basic graph. Otherwise, $G$ is called a basic graph. The following we need find all basic graphs with rank no more than 5.

Lemma 2.2.  (1) Let $G={H}_{1}\cup {H}_{2}$ , where ${H}_{1}$ and ${H}_{2}$ be two graphs. Then $r\left(G\right)=r\left({H}_{1}\right)+r\left({H}_{2}\right)$ .

(2) Let $H$ be an induced subgraph of $G$ . Then $r\left(H\right)\le r\left(G\right)$ .

Lemma 2.3. Let $G$ be a connected graph with rank $k\text{\hspace{0.17em}}\left(\ge 2\right)$ . Then there exists an induced subgraph $H$ (of $G$ ) on $k$ vertices such that $r\left(H\right)=k$ , and $\text{dist}{\text{ }}_{G}\left(u,H\right)\le 1$ for each vertex $u$ of $G$ .

Proof. Without loss of generality, suppose the previous $\text{ }k$ row vectors of $A\left(G\right)$ are linear independence, and the rest of the row vectors of $A\left(G\right)$ are linear combination of the previous $k$ row vectors. Since $A\left(G\right)$ is a symmetrical matrix, we know that the rest of the column vectors of $A\left(G\right)$ are linear combination of the previous $k$ column vectors. Therefore we can obtain the following matrix by using elementary transformation for $A\left(G\right)$ ,

$\left[\begin{array}{ll}A\left(H\right)\hfill & 0\hfill \\ 0\hfill & 0\hfill \end{array}\right]$

where $H$ is the induced subgraph (of $G$ ) with the $k$ vertices which is correspondent to the previous $k$ vectors, and $r\left(H\right)=r\left(G\right)=k$ .

Suppose $v\in V\left(G\right)$ satisfying $\text{dist}{\text{ }}_{G}\left(v,H\right)=2$ . Then there exists an induced subgraph $\text{ }F$ of $G$ such that

$A\left(F\right)=\left[\begin{array}{cccccc}0& 1& 0& 0& \dots & 0\\ 1& 0& {x}_{1}& {x}_{2}& \dots & {x}_{k}\\ 0& {x}_{1}& & & & \\ 0& {x}_{2}& & & & \\ ⋮& ⋮& & & A\left(H\right)& \\ 0& {x}_{k}& & & & \end{array}\right],$

where ${x}_{i}\in \left\{0,1\right\},i=1,2,\cdots ,k.$ Obviously, $r\left(F\right)=r\left(H\right)+2=k+2$ , this con- tradicts to $r\left(G\right)=k$ . $\square$

Let $H$ be an induced subgraph of $G$ . For a vertex subset $U$ of $V\left(H\right)$ , denote by ${S}_{U}^{H}$ (Abbreviated as ${S}_{U}$ ) the set $\left\{x\in V\left(G\right)\V\left(H\right)|{N}_{G}\left(x\right)\cap V\left(H\right)=U\right\}$ .

3. Main Result

Let $G$ be a graph with $n$ vertices, ${v}_{1},{v}_{2},\cdots ,{v}_{n}$ be ordered vertices of $G$ . $u\in V\left(G\right)$ , $n$ -dimensional column vector ${\alpha }_{u}={\left({x}_{1},{x}_{2},\cdots ,{x}_{n}\right)}^{\top }$ is called adjacency vector of $u$ , where ${x}_{i}=1$ if $u$ is adjacent to ${v}_{i}$ , and ${x}_{i}=0$ otherwise.

For obtaining all connected basic graphs with rank $r$ , we have two steps.

Step 1. Find out all graphs with rank $r$ which have exactly $r$ vertices. Denote them by ${G}_{1},{G}_{2},\cdots ,{G}_{s}$ .

Step 2. Find out all connected graphs with rank $r$ which have more than $r$ vertices. Let $G$ be a graph with rank $r$ . By Lemma 2.3, we know that $G$ contains an induced subgraph ${G}_{i}\text{\hspace{0.17em}}\left(i\in \left\{1,2,\cdots ,s\right\}\right)$ with rank $r$ and $\text{dist}{\text{ }}_{G}\left(u,{G}_{i}\right)\le 1$ for each vertices $u$ of $G$ . Therefore, we consider the adjacent relation between $u$ and the vertices of ${G}_{i}$ . Let

$\text{ }B=\left[\begin{array}{ll}A\left({G}_{i}\right)\hfill & \alpha \hfill \\ {\alpha }^{\top }\hfill & 0\hfill \end{array}\right],$

satisfying

$r\left(B\right)=r\left(A\left({G}_{i}\right)\right)=r,\text{}\left(\ast \right)$

where $A\left({G}_{i}\right)$ is adjacency matrix of ${G}_{i}$ , $\alpha =\left({x}_{1},{x}_{2},\cdots ,{x}_{r}\right)$ , ${x}_{i}\in \left\{0,1\right\}$ $\left(i=1,2,\cdots ,r\right)$ is a $|V\left({G}_{i}\right)|$ -dimensional column vector. We calculate all vectors $\alpha$ satisfying condition $\left(\ast \right)$ by MATLAB.

Obviously, $\alpha ={\left(0,0,\cdots ,0\right)}^{\top }$ and adjacency vectors of any vertex $v$ in ${G}_{i}$ satisfy $\left(\ast \right)$ ; this implies that $u$ is not adjacent to ${G}_{i}$ or $u\in {S}_{{N}_{{G}_{i}\left(v\right)}}^{{G}_{i}}$ . This is not the connected basic graphs that we need to find. Therefore, these $r+1$ 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 ${\alpha }_{1},{\alpha }_{2},\cdots ,{\alpha }_{t}$ such that $\left(\ast \right)$ holds, then for any vector ${\alpha }_{j}\text{\hspace{0.17em}}\left(j=1,2,\cdots ,t\right)$ , we can obtain a basic graph ${G}_{ij}$ on $r+1$ vertices; its adjacency matrix is

$B=\left[\begin{array}{ll}A\left({G}_{i}\right)\hfill & {\alpha }_{j}\hfill \\ {\alpha }_{j}{}^{\top }\hfill & 0\hfill \end{array}\right],$

$r\left({G}_{ij}\right)=r\left({G}_{i}\right)=r$

(In fact, suppose ${G}_{ij}$ is not a basic graph. Then it is obtained from some graph $H\left(\ncong {G}_{ij}\right)$ by multiplication of vertices. Thus there are two vertices ${v}_{s}$ and ${v}_{t}$ which are not adjacent in ${G}_{ij}$ ; the adjacent relation between ${v}_{s}$ and any vertex of ${G}_{ij}$ and the adjacent relation between ${v}_{t}$ and any vertex of ${G}_{ij}$ are the same. Since ${\alpha }_{j}$ is non-trivial vector, we have $u\notin \left\{{v}_{s},{v}_{t}\right\}$ . Hence the adjacent relation between ${v}_{s}$ and any vertex of ${G}_{ij}\u$ and the adjacent relation between ${v}_{t}$ and any vertex of ${G}_{ij}\u$ are the same. (where ${G}_{ij}\u={G}_{i}$ is the graph obtained from ${G}_{ij}$ by removing the vertex $u$ and all edges associated with $u$ ). Note ${G}_{ij}\u={G}_{i}$ , we have $r\left({G}_{i}\right) , a contradiction.)

Repeat the above process for ${G}_{ij}$ , 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 $r$ . Now we give two examples.

Example 3.1. Let $G$ be a connected graph and $r\left(G\right)=2$ , then $G\in \mathcal{M}\left({K}_{2}\right)$ .

In fact, ${K}_{2}$ is a unique graph  with rank 2 which have exactly two xertice. Calculating by MATLAB, have three and only three vectors $\alpha ={\left({x}_{1},{x}_{2}\right)}^{\top }={\left(0,0\right)}^{\top },{\left(1,0\right)}^{\top }$ and ${\left(1,0\right)}^{\top }$ satisfying that the rank of matrix $B$ is 2, and they are trivial.

$B=\left[\begin{array}{lll}0\hfill & 1\hfill & {x}_{1}\hfill \\ 1\hfill & 0\hfill & {x}_{2}\hfill \\ {x}_{1}\hfill & {x}_{2}\hfill & 0\hfill \end{array}\right]$

Hence, ${K}_{2}$ is unique basic graph with rank 2, thus $G\in \mathcal{M}\left({K}_{2}\right)$ .

Example 3.2. Let $G$ be a connected graph and $r\left(G\right)=3$ , then $G\in \mathcal{M}\left({K}_{3}\right)$ .

In fact, ${K}_{3}$ is a unique graph  with rank 3 which have exactly three vertices. Calculating by MATLAB, have four and only four vectors $\text{ }\alpha ={\left({x}_{1},{x}_{2},{x}_{3}\right)}^{\top }={\left(0,0,0\right)}^{\top },{\left(1,1,0\right)}^{\top },{\left(1,0,1\right)}^{\top }$ and ${\left(1,1,0\right)}^{\top }$ satisfying that the rank of matrix $B$ is 3, and they are trivial.

$B=\left[\begin{array}{llll}0\hfill & 1\hfill & 1\hfill & {x}_{1}\hfill \\ 1\hfill & 0\hfill & 1\hfill & {x}_{2}\hfill \\ 1\hfill & 1\hfill & 0\hfill & {x}_{3}\hfill \\ {x}_{1}\hfill & {x}_{2}\hfill & {x}_{3}\hfill & 0\hfill \end{array}\right]$

Hence, ${K}_{3}$ is unique basic graph with rank 3, thus $G\in \mathcal{M}\left({K}_{3}\right)$ .

The paper  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.  Let $G$ be a graph. Then $r\left(G\right)=4$ if and only if $G$ can be obtained from one of the graphs shown in Figure 1 by multiplication of vertices.

Theorem 3.2.  Suppose that $G$ is a graph on 5 vertices. Then $r\left(G\right)=5$ if and only if $G$ is one of the graphs shown in Figure 2.

Figure 1. Basic graph with rank 4.

Figure 2. Graphs have exactly five vertices with rank 5.

Theorem 3.3. Let $G$ be a graph without isolated vertices. Then $r\left(G\right)=5$ if and only if $G$ 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 $G$ is not connected, then $G={H}_{1}\cup {H}_{2}$ and $r\left({H}_{1}\right)=2$ , $r\left({H}_{2}\right)=3$ , where ${H}_{1}$ and ${H}_{2}$ are two graphs. By the example 1 and example 2, we have $G\in \mathcal{M}\left({K}_{2}\cup {K}_{3}\right)$ . Now assume that $G$ is connected. By Lemma 2.3, there exist induced subgraphs $H={G}_{i}\left(i=1,2,\cdots ,9\right)$ of $G$ (see Figure 2) such that $\text{dist}{\text{ }}_{G}\left(u,H\right)\le 1$ for each vertex $u$ of $G$ . According to the differences of induced subgraphs that $G$ contains, we consider the following Case 1-Case 5.

Figure 3. The basic graphs ${G}_{i}\left(i=10,11,\cdots ,25\right)$ have more than five vertices with rank 5.

Case 1. $G$ contains an induced subgraph ${G}_{1}={K}_{5}$ , $V\left({G}_{1}\right)=\left\{1,2,3,4,5\right\}$ ,

$A\left({G}_{1}\right)=\left[\begin{array}{lllll}0\hfill & 1\hfill & 1\hfill & 1\hfill & 1\hfill \\ 1\hfill & 0\hfill & 1\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 0\hfill & 1\hfill & 1\hfill \\ 1\hfill & 1\hfill & 1\hfill & 0\hfill & 1\hfill \\ 1\hfill & 1\hfill & 1\hfill & 1\hfill & 0\hfill \end{array}\right].$

The following we first determine basic graph contain $\text{ }{G}_{1}.$ Let

$B=\left[\begin{array}{ll}A\left({G}_{1}\right)\hfill & {\alpha }^{\top }\hfill \\ \alpha \hfill & 0\hfill \end{array}\right]$

where $\alpha =\left({x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}\right)$ , ${x}_{i}\in \left\{0,1\right\}$ $\left(i=1,2,\cdots ,5\right)$ . For $\alpha$ satisfying $r\left(B\right)=r\left(A\left({G}_{1}\right)\right)=5$ (or $\mathrm{det}\left(B\right)=0$ ), calculating by MATLAB, we obtain

$\alpha =\left(0,0,0,0,0\right),\left(0,1,1,1,1\right),\left(1,0,1,1,1\right),\left(1,1,0,1,1\right),\left(1,1,1,0,1\right),\text{ }\text{or}\text{ }\text{}\text{\hspace{0.17em}}\left(1,1,1,1,0\right).$

This implies that not exist non-trivial vectors such that $r\left(B\right)=5$ , hence ${G}_{1}$ is unique basic graph contain ${G}_{1}$ with rank 5, then $G\in \mathcal{M}\left({G}_{1}\right)$ .

Case 2. $G$ contains an induced subgraph ${G}_{2}={C}_{5}$ , $V\left({G}_{2}\right)=\left\{1,2,3,4,5\right\}$ . Similar with Case 1, we know $G\in \mathcal{M}\left({G}_{2}\right)$ .

Case 3. $G$ contains an induced subgraph ${G}_{3}$ , $V\left({G}_{3}\right)=\left\{1,2,3,4,5\right\}$ . Similar with Case 1, we know $G\in \mathcal{M}\left({G}_{3}\right)$ .

Case 4. $G$ contains an induced subgraph ${G}_{4}$ , $V\left({G}_{4}\right)=\left\{1,2,3,4,5\right\}$ ,

$A\left({G}_{4}\right)=\left[\begin{array}{lllll}0\hfill & 1\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 1\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill & 1\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right].$

First considering basic graph contain ${G}_{4}$ , let

$B=\left[\begin{array}{ll}A\left({G}_{4}\right)\hfill & {\alpha }^{\top }\hfill \\ \alpha \hfill & 0\hfill \end{array}\right]$

where $\alpha =\left({x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5}\right)$ , ${x}_{i}\in \left\{0,1\right\}$ $\left(i=1,2,\cdots ,5\right)$ . For $\alpha$ satisfying $r\left(B\right)=5$ , calculating by MATLAB, we obtain

$\begin{array}{c}\alpha =\left(0,0,0,0,0\right),\left(0,1,1,0,0\right),\left(1,0,1,0,0\right),\left(1,1,0,1,0\right),\left(0,0,1,0,1\right),\left(0,0,0,1,0\right),\\ \left(1,0,1,1,0\right),\left(0,1,1,1,0\right),\left(1,0,0,1,1\right),\left(0,1,0,1,1\right),\left(1,1,0,0,0\right).\end{array}$

we know the first six vectors is trivial.

Case 4.1. For non-trivial vector $\alpha =\left(0,1,1,1,0\right)$ , (or $\left(1,0,1,1,0\right)$ ), then there exists a graph ${G}_{10}$ (the adjacency matrix of ${G}_{10}$ is B), it is a basic graph contain ${G}_{4}$ with rank 5. $V\left({G}_{10}\right)=\left\{1,2,3,4,5,6\right\}$ , Same as above, calculating by MATLAB for ${G}_{10}$ , we obtain 3 non-trivial vectors. $\alpha =\left(0,1,0,1,1,1\right),\left(1,0,1,1,0,1\right)$ , (or $\left(1,1,0,0,0,1\right)$ ).

Case 4.1.1. For non-trivial vector $\alpha =\left(0,1,0,1,1,1\right)$ , then there exists a graph ${G}_{11}$ is a basic graph contain ${G}_{10}$ with rank 5. Same as above, calculating by MATLAB for ${G}_{11}$ , we obtain not exist non-trivial vectors. Hence ${G}_{11}$ is a unique basic graph contain ${G}_{11}$ with rank 5.

Case 4.1.2. For non-trivial vector $\alpha =\left(1,0,1,1,0,1\right)$ , then there exists a graph ${G}_{12}$ is a basic graph contain ${G}_{10}$ with rank 5. Same as above, calculating by MATLAB for ${G}_{12}$ , we obtain not exist non-trivial vectors $\left(1,1,0,0,0,1,1\right)$ , the resulting produce a graph ${G}_{13}$ is a basic graph contain ${G}_{12}$ with rank 5. Calculating by MATLAB for ${G}_{13}$ , we obtain not exist non-trivial vectors, Hence ${G}_{13}$ is a unique basic graph contain ${G}_{13}$ with rank 5.

Case 4.1.3. For non-trivial vector $\alpha =\left(1,1,0,0,0,1\right)$ , then there exists a graph ${G}_{14}$ is a basic graph contain ${G}_{10}$ with rank 5. Calculating by MATLAB for ${G}_{14}$ , we obtain exist a non-trivial vectors $\alpha =\left(1,0,1,1,0,1,1\right)$ . The resulting produce a graph ${G}_{13}$ is a basic graph contain ${G}_{14}$ with rank 5. Similar with Case 4.1.2, ${G}_{13}$ is a unique basic graph contain ${G}_{13}$ with rank 5.

Case 4.2. For non-trivial vector $\alpha =\left(0,1,0,1,1\right)$ ,(or $\left(1,0,0,1,1\right)$ ), then there exists a graph ${G}_{15}$ is a basic graph contain ${G}_{4}$ with rank 5. $V\left({G}_{15}\right)=1,2,3,4,5,6$ , Same as above, calculating by MATLAB for ${G}_{15}$ , we obtain 3 non-trivial vectors. $\alpha =\left(1,1,1,0,1,0\right),\left(1,0,0,1,1,1\right)$ , (or $\left(0,1,1,1,0,1\right)$ ).

Case 4.2.1. For non-trivial vector $\alpha =\left(1,1,1,0,1,0\right)$ , (or $\left(1,0,0,1,1,1\right)$ ), then there exists a graph ${G}_{16}$ is a basic graph contain ${G}_{15}$ with rank 5. Same as above, calculating by MATLAB for ${G}_{16}$ exist a non-trivial vectors $\left(1,0,0,1,0,1,1\right)$ , the resulting produce a graph ${G}_{17}$ is a basic graph contain ${G}_{16}$ with rank 5. Calculating with MATLAB for ${G}_{17}$ , we obtain not exist non-trivial vectors. Hence ${G}_{17}$ is a unique basic graph contain ${G}_{17}$ with rank 5.

Case 4.2.2. For non-trivial vector $\alpha =\left(0,1,1,1,0,1\right)$ , then there exists a graph ${G}_{11}$ is a basic graph contain ${G}_{15}$ with rank 5. Similar with Case 4.1.1, ${G}_{11}$ is a unique basic graph contain ${G}_{11}$ with rank 5.

Case 4.3. For non-trivial vector $\alpha =\left(1,1,0,0,0\right)$ , there exists a graph ${G}_{18}$ is a basic graph contain ${G}_{4}$ with rank 5. Same as above, calculating by MATLAB for ${G}_{18}$ , we obtain three non-trivial vectors $\alpha =\left(1,1,1,0,1,0\right),\left(0,1,1,1,0,1\right)$ , (or $\left(1,0,1,1,0,1\right)$ ).

Case 4.3.1. For non-trivial vector $\alpha =\left(1,1,1,0,1,0\right)$ , there exists a graph ${G}_{19}$ is a basic graph contain ${G}_{18}$ with rank 5. Same as above, calculating by MATLAB for ${G}_{19}$ , we obtain not exist non-trivial vectors. Hence ${G}_{19}$ is a unique basic graph contain ${G}_{19}$ with rank 5.

Case 4.3.2. For non-trivial vector $\alpha =\left(0,1,1,1,0,1\right)$ ,(or $\alpha =\left(1,0,1,1,0,1\right)$ ), there exists a graph ${G}_{14}$ is a basic graph included ${G}_{18}$ with rank 5. Similar with Case 4.1.3, we obtain ${G}_{13}$ and ${G}_{14}$ it is only one basic graph contain ${G}_{14}$ with rank 5.

In a word, basic graph contain ${G}_{4}$ with rank 5 are ${G}_{4}$ , ${G}_{i}\left(i=10,11,\cdots ,19\right)$ . Let $G$ be a graph contain ${G}_{4}$ with rank 5, then it must be a multiplication of vertices graph of one of ${G}_{4}$ , ${G}_{i}\left(i=10,11,\cdots ,19\right)$ , thus $G\in \mathcal{M}\left({G}_{i}\right)\left(i=4,10,11,\cdots ,19\right)$ .

Case 5. $G$ contains an induced subgraph which is ${G}_{i}\left(i=5,6,7,8\right)$ , similar with Case 4, we first find basic graphs contain ${G}_{i}$ 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 ${G}_{i}\left(i=4,5,\cdots ,9\right)$ with rank 5.

Summarize the previous cases, we can obtain $G\in \mathcal{M}\left({G}_{i}\right)\left(i=1,2,\cdots ,25\right)$ .

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 $G$ be a graph, then $r\left(G\right)\le 5$ if and only if $G\in \mathcal{M}\left(H\right)$ , where $H$ is an induced subgraph of ${G}_{1},{G}_{2},{G}_{3},{G}_{11},{G}_{13},{G}_{17},{G}_{19}$ and ${G}_{24}$ (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).

Conflicts of Interest

The authors declare no conflicts of interest.

  Collatz, L. and Sinogowitz, U. (1957) Spektren endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 21, 63-77. https://doi.org/10.1007/BF02941924  Cheng, B. and Liu, B. (2011) On the Nullity of Tricyclic Graphs. Linear Algebra and Its Applications, 434, 1799-1810. https://doi.org/10.1016/j.laa.2011.01.006  Sciriha, I. (1998) On the Construction of Graphs of Nullity One. Discrete Mathematics, 181,193-211. https://doi.org/10.1016/S0012-365X(97)00036-8  Cvetkovic', D. and Gutman, I. (1972) The Algebraic Multiplicity of the Number Zero in the Spectrum of a Bipartite Graph. Matematicki Vesnik, 9, 141-150.  Cvetkovic’, D., Gutman, I. and Trinajstic’, N. (1975) Graphical Studies on the Relations between the Structure and Reactivity of Conjugated System: The Role of Non-Bonding Molecular Orbitals. Journal of Molecular Structure, 28, 289-303. https://doi.org/10.1016/0022-2860(75)80099-8  Golumbic, M.C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.  Cvetkovic', D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.  Cheng, B. and Liu, B. (2007) On the Nullity of Graphs. Electronic Journal of Linear Algebra, 16, 60-67. https://doi.org/10.13001/1081-3810.1182  Chang, G.J., Huang, L.H. and Yeh, H.G. (2011) A Characterization of Graphs with Rank 4. Linear Algebra and Its Applications, 434, 1793-1798. https://doi.org/10.1016/j.laa.2010.09.040  Chang, G.J. Huang, L.H. and Yeh, H.G. (2012) A Characterization of Graphs with Rank 5. Linear Algebra and Its Applications, 436, 4241-4250. https://doi.org/10.1016/j.laa.2012.01.021

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc. This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.