Applied Mathematics
Vol.08 No.01(2017), Article ID:73681,9 pages
10.4236/am.2017.81003

A Characterization of Graphs with Rank No More Than 5

Haicheng Ma, Xiaohua Liu

Department of Mathematics, Qinghai Nationalities University, Xining, China

Copyright © 2017 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: December 4, 2016; Accepted: January 19, 2017; Published: January 22, 2017

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.

Keywords:

Graph, Matrix, Rank, Nullity

1. Introduction

In this paper only consider simple graph of finite and unordered. G = ( V ( G ) , E ( G ) ) is a graph, V ( G ) = { v 1 , v 2 , , v n } is vertices set of a graph G , the adjacency matrix A ( G ) of a graph G is the n × n symmetric matrix [ a i j ] such that a i j = 1 if v i is adjacent to v j , and a i j = 0 otherwise. Obviously, A ( G ) 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 ( G ) , is defined to be the number of the rank of matrix A ( G ) . The nullity of a graph G is the multiplicity of the zero eigenvalues of matrix A ( G ) and denoted by η ( G ) . Clearly, η ( G ) + r ( G ) = | V ( G ) | . 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 ( G ) 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 ( G ) is equal to 2 or 3, which is completely characterized in [8] . The graph G with the rank r ( G ) 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 ( x ) . The distance between u and v , denoted by dist G ( u , v ) , is the length of a shortest u , v -path in graph G . The distance between a vertex u and a subgraph H of G , denoted by dist G ( u , H ) , is defined to be the value min { dist G ( u , v ) : v V ( H ) } . Given a subset S V ( G ) , the subgraph of G induced by S , is written as G [ S ] . The n -path, the n -cycle and the n - complete graph are denoted by P n , C n and K n , respectively.

A subset I V ( G ) is called an independent set of G if the subgraph G [ I ] is a null graph. Next we define a graph operation (see page 53 of [6] ). Give a graph G with V ( G ) = { v 1 , v 2 , , v n } . Let m = ( m 1 , m 2 , , m n ) be a vector of positive integers. Denoted by G 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 , , 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 m is said to be obtained from G by multi- plication of vertices. For graphs G 1 , G 2 , , G k , we denote by M ( G 1 , G 2 , , G k ) the class of all graphs that can be obtained from one of the graphs in { G 1 , G 2 , , G k } by multiplication of vertices.

2. Preliminaries

Lemma 2.1. [9] Suppose that G and H are two graphs. If G M ( H ) , then r ( G ) = r ( H ) .

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 ( G ) such that G M ( H ) , 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 H 2 , where H 1 and H 2 be two graphs. Then r ( G ) = r ( H 1 ) + r ( H 2 ) .

(2) Let H be an induced subgraph of G . Then r ( H ) r ( G ) .

Lemma 2.3. Let G be a connected graph with rank k ( 2 ) . Then there exists an induced subgraph H (of G ) on k vertices such that r ( H ) = k , and dist G ( u , H ) 1 for each vertex u of G .

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

[ A ( H ) 0 0 0 ]

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

Suppose v V ( G ) satisfying dist G ( v , H ) = 2 . Then there exists an induced subgraph F of G such that

A ( F ) = [ 0 1 0 0 0 1 0 x 1 x 2 x k 0 x 1 0 x 2 A ( H ) 0 x k ] ,

where x i { 0 , 1 } , i = 1 , 2 , , k . Obviously, r ( F ) = r ( H ) + 2 = k + 2 , this con- tradicts to r ( G ) = k .

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

3. Main Result

Let G be a graph with n vertices, v 1 , v 2 , , v n be ordered vertices of G . u V ( G ) , n -dimensional column vector α u = ( x 1 , x 2 , , x n ) 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 , , 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 ( i { 1 , 2 , , s } ) with rank r and dist G ( u , G i ) 1 for each vertices u of G . Therefore, we consider the adjacent relation between u and the vertices of G i . Let

B = [ A ( G i ) α α 0 ] ,

satisfying

r ( B ) = r ( A ( G i ) ) = r , ( )

where A ( G i ) is adjacency matrix of G i , α = ( x 1 , x 2 , , x r ) , x i { 0 , 1 } ( i = 1 , 2 , , r ) is a | V ( G i ) | -dimensional column vector. We calculate all vectors α satisfying condition ( ) by MATLAB.

Obviously, α = ( 0 , 0 , , 0 ) and adjacency vectors of any vertex v in G i satisfy ( ) ; this implies that u is not adjacent to G i or u S N G i ( v ) 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 α 1 , α 2 , , α t such that ( ) holds, then for any vector α j ( j = 1 , 2 , , t ) , we can obtain a basic graph G i j on r + 1 vertices; its adjacency matrix is

B = [ A ( G i ) α j α j 0 ] ,

r ( G i j ) = r ( G i ) = r

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

Repeat the above process for G i j , 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 ( G ) = 2 , then G M ( K 2 ) .

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 α = ( x 1 , x 2 ) = ( 0 , 0 ) , ( 1 , 0 ) and ( 1 , 0 ) satisfying that the rank of matrix B is 2, and they are trivial.

B = [ 0 1 x 1 1 0 x 2 x 1 x 2 0 ]

Hence, K 2 is unique basic graph with rank 2, thus G M ( K 2 ) .

Example 3.2. Let G be a connected graph and r ( G ) = 3 , then G M ( K 3 ) .

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 α = ( x 1 , x 2 , x 3 ) = ( 0 , 0 , 0 ) , ( 1 , 1 , 0 ) , ( 1 , 0 , 1 ) and ( 1 , 1 , 0 ) satisfying that the rank of matrix B is 3, and they are trivial.

B = [ 0 1 1 x 1 1 0 1 x 2 1 1 0 x 3 x 1 x 2 x 3 0 ]

Hence, K 3 is unique basic graph with rank 3, thus G M ( K 3 ) .

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 ( G ) = 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 ( G ) = 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 ( G ) = 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 H 2 and r ( H 1 ) = 2 , r ( H 2 ) = 3 , where H 1 and H 2 are two graphs. By the example 1 and example 2, we have G M ( K 2 K 3 ) . Now assume that G is connected. By Lemma 2.3, there exist induced subgraphs H = G i ( i = 1 , 2 , , 9 ) of G (see Figure 2) such that dist G ( u , H ) 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 ( i = 10 , 11 , , 25 ) have more than five vertices with rank 5.

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

A ( G 1 ) = [ 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 ] .

The following we first determine basic graph contain G 1 . Let

B = [ A ( G 1 ) α α 0 ]

where α = ( x 1 , x 2 , x 3 , x 4 , x 5 ) , x i { 0,1 } ( i = 1 , 2 , , 5 ) . For α satisfying r ( B ) = r ( A ( G 1 ) ) = 5 (or det ( B ) = 0 ), calculating by MATLAB, we obtain

α = ( 0 , 0 , 0 , 0 , 0 ) , ( 0 , 1 , 1 , 1 , 1 ) , ( 1 , 0 , 1 , 1 , 1 ) , ( 1 , 1 , 0 , 1 , 1 ) , ( 1 , 1 , 1 , 0 , 1 ) , or ( 1 , 1 , 1 , 1 , 0 ) .

This implies that not exist non-trivial vectors such that r ( B ) = 5 , hence G 1 is unique basic graph contain G 1 with rank 5, then G M ( G 1 ) .

Case 2. G contains an induced subgraph G 2 = C 5 , V ( G 2 ) = { 1 , 2 , 3 , 4 , 5 } . Similar with Case 1, we know G M ( G 2 ) .

Case 3. G contains an induced subgraph G 3 , V ( G 3 ) = { 1 , 2 , 3 , 4 , 5 } . Similar with Case 1, we know G M ( G 3 ) .

Case 4. G contains an induced subgraph G 4 , V ( G 4 ) = { 1 , 2 , 3 , 4 , 5 } ,

A ( G 4 ) = [ 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 ] .

First considering basic graph contain G 4 , let

B = [ A ( G 4 ) α α 0 ]

where α = ( x 1 , x 2 , x 3 , x 4 , x 5 ) , x i { 0,1 } ( i = 1 , 2 , , 5 ) . For α satisfying r ( B ) = 5 , calculating by MATLAB, we obtain

α = ( 0 , 0 , 0 , 0 , 0 ) , ( 0 , 1 , 1 , 0 , 0 ) , ( 1 , 0 , 1 , 0 , 0 ) , ( 1 , 1 , 0 , 1 , 0 ) , ( 0 , 0 , 1 , 0 , 1 ) , ( 0 , 0 , 0 , 1 , 0 ) , ( 1 , 0 , 1 , 1 , 0 ) , ( 0 , 1 , 1 , 1 , 0 ) , ( 1 , 0 , 0 , 1 , 1 ) , ( 0 , 1 , 0 , 1 , 1 ) , ( 1 , 1 , 0 , 0 , 0 ) .

we know the first six vectors is trivial.

Case 4.1. For non-trivial vector α = ( 0 , 1 , 1 , 1 , 0 ) , (or ( 1 , 0 , 1 , 1 , 0 ) ), 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 ( G 10 ) = { 1 , 2 , 3 , 4 , 5 , 6 } , Same as above, calculating by MATLAB for G 10 , we obtain 3 non-trivial vectors. α = ( 0 , 1 , 0 , 1 , 1 , 1 ) , ( 1 , 0 , 1 , 1 , 0 , 1 ) , (or ( 1 , 1 , 0 , 0 , 0 , 1 ) ).

Case 4.1.1. For non-trivial vector α = ( 0 , 1 , 0 , 1 , 1 , 1 ) , 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 α = ( 1 , 0 , 1 , 1 , 0 , 1 ) , 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 ( 1 , 1 , 0 , 0 , 0 , 1 , 1 ) , 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 α = ( 1 , 1 , 0 , 0 , 0 , 1 ) , 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 α = ( 1 , 0 , 1 , 1 , 0 , 1 , 1 ) . 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 α = ( 0 , 1 , 0 , 1 , 1 ) ,(or ( 1 , 0 , 0 , 1 , 1 ) ), then there exists a graph G 15 is a basic graph contain G 4 with rank 5. V ( G 15 ) = 1 , 2 , 3 , 4 , 5 , 6 , Same as above, calculating by MATLAB for G 15 , we obtain 3 non-trivial vectors. α = ( 1 , 1 , 1 , 0 , 1 , 0 ) , ( 1 , 0 , 0 , 1 , 1 , 1 ) , (or ( 0 , 1 , 1 , 1 , 0 , 1 ) ).

Case 4.2.1. For non-trivial vector α = ( 1 , 1 , 1 , 0 , 1 , 0 ) , (or ( 1 , 0 , 0 , 1 , 1 , 1 ) ), 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 ( 1 , 0 , 0 , 1 , 0 , 1 , 1 ) , 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 α = ( 0 , 1 , 1 , 1 , 0 , 1 ) , 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 α = ( 1 , 1 , 0 , 0 , 0 ) , 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 α = ( 1 , 1 , 1 , 0 , 1 , 0 ) , ( 0 , 1 , 1 , 1 , 0 , 1 ) , (or ( 1 , 0 , 1 , 1 , 0 , 1 ) ).

Case 4.3.1. For non-trivial vector α = ( 1 , 1 , 1 , 0 , 1 , 0 ) , 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 α = ( 0 , 1 , 1 , 1 , 0 , 1 ) ,(or α = ( 1 , 0 , 1 , 1 , 0 , 1 ) ), 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 ( i = 10 , 11 , , 19 ) . 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 ( i = 10 , 11 , , 19 ) , thus G M ( G i ) ( i = 4 , 10 , 11 , , 19 ) .

Case 5. G contains an induced subgraph which is G i ( i = 5 , 6 , 7 , 8 ) , 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 ( i = 4 , 5 , , 9 ) with rank 5.

Summarize the previous cases, we can obtain G M ( G i ) ( i = 1 , 2 , , 25 ) .

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 ( G ) 5 if and only if G M ( H ) , 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.C. and Liu, X.H. (2017) A Characterization of Graphs with Rank No More Than 5. Applied Mathematics, 8, 26-34. http://dx.doi.org/10.4236/am.2017.81003

References

  1. 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. 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. 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. 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. 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. 6. Golumbic, M.C. (1980) Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.

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

  8. 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. 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. 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