A Characterization of Graphs with Rank No More Than 5

Abstract

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.

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.

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\times 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 \mathrm{(}G\mathrm{)}+r\mathrm{(}G\mathrm{)=|}V\mathrm{(}G\mathrm{)|}$ . In chemistry, the nullity is correlated with the stability of hydrocarbon that a graph $G$ 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 $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 [8] . The graph $G$ with the rank $r\left(G\right)$ 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 $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{\hspace{0.05em}}u$ and $v$ , denoted by $\text{dist}{\text{\hspace{0.05em}}}_{G}\left(u,v\right)$ , is the length of a shortest $u$ , $v$ -path in graph $G$ . The distance between a vertex $\text{\hspace{0.05em}}u$ and a subgraph $H$ of $G$ , denoted by $\text{dist}{\text{\hspace{0.05em}}}_{G}\left(u\mathrm{,}H\right)$ , is defined to be the value $\mathrm{min}\left\{\text{dist}{\text{\hspace{0.05em}}}_{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{\hspace{0.05em}}{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 [6] ). 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}\mathrm{,}{G}_{2}\mathrm{,}\cdots \mathrm{,}{G}_{k}$ , we denote by $\mathcal{M}\left({G}_{1}\mathrm{,}{G}_{2}\mathrm{,}\cdots \mathrm{,}{G}_{k}\right)$ the class of all graphs that can be obtained from one of the graphs in $\left\{{G}_{1}\mathrm{,}{G}_{2}\mathrm{,}\cdots \mathrm{,}{G}_{k}\right\}$ by multiplication of vertices.

2. Preliminaries

Lemma 2.1. [9] 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. [3] (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{\hspace{0.05em}}}_{G}\left(u\mathrm{,}H\right)\le 1$ for each vertex $u$ of $G$ .

Proof. Without loss of generality, suppose the previous $\text{\hspace{0.05em}}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{\hspace{0.05em}}}_{G}\left(v\mathrm{,}H\right)=2$ . Then there exists an induced subgraph $\text{\hspace{0.05em}}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}& & & & \\ \vdots & \vdots & & & 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)\backslash 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}\mathrm{,}{v}_{2}\mathrm{,}\cdots \mathrm{,}{v}_{n}$ be ordered vertices of $G$ . $u\in V\left(G\right)$ , $n$ -dimensional column vector ${\alpha}_{u}={\left({x}_{1}\mathrm{,}{x}_{2}\mathrm{,}\cdots \mathrm{,}{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}\mathrm{,}{G}_{2}\mathrm{,}\cdots \mathrm{,}{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{\hspace{0.05em}}}_{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{\hspace{0.05em}}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{}(\ast )$

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 $\left|V\left({G}_{i}\right)\right|$ -dimensional column vector. We calculate all vectors $\alpha $ satisfying condition $(\ast )$ by MATLAB.

Obviously, $\alpha ={\left(0,0,\cdots ,0\right)}^{\top}$ and adjacency vectors of any vertex $v$ in ${G}_{i}$ satisfy $(\ast )$ ; 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}\mathrm{,}{\alpha}_{2}\mathrm{,}\cdots \mathrm{,}{\alpha}_{t}$ such that $(\ast )$ 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}\mathrm{,}{v}_{t}\right\}$ . Hence the adjacent relation between ${v}_{s}$ and any vertex of ${G}_{ij}\backslash u$ and the adjacent relation between ${v}_{t}$ and any vertex of ${G}_{ij}\backslash u$ are the same. (where ${G}_{ij}\backslash u={G}_{i}$ is the graph obtained from ${G}_{ij}$ by removing the vertex $u$ and all edges associated with $u$ ). Note ${G}_{ij}\backslash u={G}_{i}$ , we have $r\left({G}_{i}\right)<r$ , 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 [7] 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 [7] with rank 3 which have exactly three vertices. Calculating by MATLAB, have four and only four vectors $\text{\hspace{0.05em}}\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 [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 $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. [7] 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{\hspace{0.05em}}}_{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{\hspace{0.05em}}{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\{\mathrm{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{\hspace{0.05em}}\text{or}\text{\hspace{0.05em}}\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\{\mathrm{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).

Cite this paper

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.

Ma, H. and Liu, X. (2017) A Characterization of Graphs with Rank No More Than 5.

References

[1] 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

[2] 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

[3] 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

[4] 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.

[5] 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

[6] Golumbic, M.C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

[7] Cvetkovic', D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.

[8] 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

[9] 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

[10] 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