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. 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 1. Basic graph with rank 4.
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).
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. 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