Journal of Applied Mathematics and Physics
Vol.08 No.02(2020), Article ID:98057,7 pages
10.4236/jamp.2020.82019
Graphs with Pendant Vertices and
Haicheng Ma*, Shang Gao, Danyang Li
Department of Mathematics, Qinghai Nationalities University Xining, Qinghai, China
Copyright © 2020 by author(s) 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: January 6, 2020; Accepted: January 19, 2020; Published: January 22, 2020
ABSTRACT
Let G be a graph of order n with vertex set . the adjacency matrix of G is an matrix , where is the number edges joining and in G. The eigenvalues of are said to be the eigenvalues of the graph G and to form the spectrum of this graph. The number of nonzero eigenvalues and zero eigenvalues in the spectrum of G are called rank and nullity of the graph G, and are denoted by and , respectively. It follows from the definitions that . 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.
Keywords:
Adjacency Matrix, Rank, Nullity, Multiplication of Vertices
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 1. The basic graphs of rank 4.
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).
Conflicts of Interest
The authors declare no conflicts of interest regarding the publication of this paper.
Cite this paper
Ma, H.C., Gao, S. and Li, D.Y. (2020) Graphs with Pendant Vertices and r (G) ≤ 7. Journal of Applied Mathematics and Physics, 8, 240-246. https://doi.org/10.4236/jamp.2020.82019
References
- 1. Cheng, B. and Liu. B. (2007) On the Nullity of Graphs. The Electronic Journal of Linear Algebra, 16, 60-67.
- 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. Collatz, L. and Sinogowitz, U. (1957) Spektren endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 21, 63-77. https://doi.org/10.1007/BF02941924
- 4. Fan, Y. and Qian, K. (2009) On the Nullity of Bipartite Graphs. Linear Algebra and Its Applications, 430, 2943-2949. https://doi.org/10.1016/j.laa.2009.01.007
- 5. Fiorini, S., Gutman, I. and Sciriha, I. (2005) Trees with Maximum Nullity. Linear Algebra and Its Applications, 397, 245-251. https://doi.org/10.1016/j.laa.2004.10.024
- 6. Gong, S., Fan, Y. and Yin, Z. (2010) On the Nullity of Graphs with Pendant Trees. Linear Algebra and Its Applications, 433, 1374-1380. https://doi.org/10.1016/j.laa.2010.05.016
- 7. Hu, S., Liu, B. and Tan, X. (2008) On the Nullity of Bicyclic Graphs. Linear Algebra and Its Applications, 429, 1387-1391. https://doi.org/10.1016/j.laa.2007.12.007
- 8. Li, S. (2008) On the Nullity of Graphs with Pendant Vertices. Linear Algebra and Its Applications, 429, 1619-1628. https://doi.org/10.1016/j.laa.2008.04.037
- 9. Nath, M. and Sarma, B. (2007) On the Null-Spaces of Acyclic and Unicyclic Singular Graphs. Linear Algebra and Its Applications, 427, 42-54. https://doi.org/10.1016/j.laa.2007.06.017
- 10. 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
- 11. Sciriha, I. and Gutman, I. (2001) On the Nullity of line Graphs of Trees. Discrete Mathematics, 232, 35-45. https://doi.org/10.1016/S0012-365X(00)00187-4
- 12. Tang, X. and Liu, B. (2005) On the Nullity of Unicyclic Graphs. Linear Algebra and Its Applications, 408, 212-220. https://doi.org/10.1016/j.laa.2005.06.012
- 13. Sciriha, I. (1999) On the Rank of Graphs. In: Alavi, Y., Lick, D. and Schwenk, A., Eds., Combinatorics, Graph Theory, and Algorithms, Volume II, New Issue Press, Western Michigan University, Kalamazoo, MI, 769-778.
- 14. Chang, G., Huang, L. and Yeh, H. (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
- 15. Chang, G., Huang, L. and Yeh, H. (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
- 16. Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.