Graphs with Pendant Vertices and r(G) ≤ 7

Show more

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: $A\left(G\right)={\left({a}_{ij}\right)}_{n\times n}$

${a}_{ij}=(\begin{array}{cc}1& \text{if}\text{\hspace{0.17em}}i\sim j\text{,}\\ 0& \text{others}\text{.}\end{array}$

Obviously, $A\left(G\right)$ 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 $A\left(G\right)$ 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 $r\left(G\right)$ and $\eta \left(G\right)$ respectively. Obviously $r\left(G\right)+\eta \left(G\right)=n$ . 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 $r\left(G\right)=0$ if and only if G is an empty graph without edges. Obviously, there is no graph G where $r\left(G\right)=1$ . In [1] [13], graph G is characterized where $r\left(G\right)=2,3$ . In [2] [14], graph G is characterized where $r\left(G\right)=4$ . In [15], graph G is characterized where $r\left(G\right)=5$ . In this paper, by using the operation of multiplication of vertices, a characterization for graph G with pendant vertices and $r\left(G\right)=7$ is shown, and then a characterization for graph G with pendant vertices and $r\left(G\right)$ 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 $r\left(G\right)=7$ is shown, and then a characterization for graph G with pendant vertices and $r\left(G\right)\le 7$ is shown.

Let G be a graph, for a vertex $x\in V\left(G\right)$ , define ${N}_{G}\left(x\right)$ to be the neighborhood of vertex x in G. A vertex subset $I\subseteq V\left(G\right)$ of a graph G is an independent set of G if $G\left[I\right]$ , the subgraph induced by I, is edgeless. Now let us introduce a graph operation. Let $V\left(G\right)=\left\{{v}_{1}\mathrm{,}{v}_{2}\mathrm{,}\cdots \mathrm{,}{v}_{n}\right\}$ , and $m=\left({m}_{1}\mathrm{,}{m}_{2}\mathrm{,}\cdots ,{m}_{n}\right)$ be a vector of positive integers. Denote by $G\circ m$ the graph obtained from G by replacing each vertex ${v}_{i}$ of G with an independent set of ${m}_{i}$ vertices $\left\{{v}_{i}^{1}\mathrm{,}{v}_{i}^{2}\mathrm{,}\cdots ,{v}_{i}^{{m}_{i}}\right\}$ 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 multiplication of vertices. Let $\Lambda $ be the set of some graphs, we denote by $\mathcal{M}\left(\Lambda \right)$ class of all graphs that can be constructed from one of the graphs in $\Lambda $ by multiplication of vertices. ${K}_{n}$ denotes the complete graph on n vertices. Undefined concepts and notations will follow [16].

2. Some Lemmas

Lemma 2.1. [1]

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

2) Let H be a vertex-induced subgraph of G, then $r\left(H\right)\le r\left(G\right)$ .

Lemma 2.2. [14] Let G and H be two graphs, if $G\in \mathcal{M}\left(H\right)$ , then $r\left(H\right)=r\left(G\right)$ .

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 ${K}_{2}$ and the connected basic graph of rank 3 is ${K}_{3}$ . For convenience, let’s say ${\Lambda}_{2}=\left\{{K}_{2}\right\}$ , ${\Lambda}_{3}=\left\{{K}_{3}\right\}$ ; 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 $r\left(G\right)=4$ if and only if $G\in \mathcal{M}\left({\Lambda}_{4}\right)$ , where ${\Lambda}_{4}=\left\{{H}_{1}\mathrm{,}{H}_{2}\mathrm{,}\cdots \mathrm{,}{H}_{9}\right\}$ , every ${H}_{i}\left(i=1,2,\cdots ,9\right)$ is shown in Figure 1.

Lemma 2.4. [15] Let G be a graph without isolated vertices, then $r\left(G\right)=5$ if and only if $G\in \mathcal{M}\left({\Lambda}_{5}\right)$ , where ${\Lambda}_{5}=\left\{{G}_{1},{G}_{2},\cdots ,{G}_{25}\right\}$ , every ${G}_{i}\left(i=1,2,\cdots ,25\right)$ 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 $\eta \left(G\right)=\eta \left(H\right)$ , equivalently $r\left(G\right)=r\left(H\right)+2$ .

3. Main Conclusions

Let H be a graph with $V\left(H\right)=\left\{{v}_{1}\mathrm{,}{v}_{2}\mathrm{,}\cdots ,{v}_{n}\right\}$ , and $m=\left({m}_{1},{m}_{2},\cdots ,{m}_{n}\right)$ is a vector with ${m}_{i}=1$ or 2, ( $i=1,2,\cdots ,n$ ). Then $V\left(H\right)$ can be divided into two sets: ${V}_{1}=\left\{{v}_{i}\in V\left(H\right)|{m}_{i}=1\right\}$ and ${V}_{2}=\left\{{v}_{i}\in V\left(H\right)|{m}_{i}=2\right\}$ . Let ${v}_{i}^{1}$ and ${v}_{i}^{2}$ be the vertices in $H\circ m$ by multiplying the vertex ${v}_{i}$ in H when ${m}_{i}=2$ . For a subset $U\subseteq {V}_{1}$ , we construct a graph ${\left(H\circ m\right)}^{U}$ as follows:

$V\left({\left(H\circ m\right)}^{U}\right)=\left\{x\mathrm{,}y\right\}\cup V\left(H\circ m\right)$

$E\left({\left(H\circ m\right)}^{U}\right)=\left\{xy\right\}\cup \left\{y{v}_{i}^{1}|\forall i,\text{\hspace{0.17em}}{m}_{i}=2\right\}\cup \left\{y{v}_{i}|{v}_{i}\in U\right\}\cup E\left(H\circ m\right).$

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, ${\left(H\circ m\right)}^{U}$ has a pendant vertex x.

Lemma 3.1. If H is a basic graph, then ${\left(H\circ m\right)}^{U}$ is also a basic graph.

Proof. For any $i\mathrm{,}j\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ , if $i\ne j$ , as H is a basic graph, then ${N}_{H}\left({v}_{i}\right)\ne {N}_{H}\left({v}_{j}\right)$ . by the definition of the graph ${\left(H\circ m\right)}^{U}$ , we have ${N}_{{\left(H\circ m\right)}^{U}}\left({v}_{i}^{s}\right)={N}_{H}\left({v}_{i}\right)$ or ${N}_{H}\left({v}_{i}\right)\cup \left\{y\right\}$ , either way, we have ${N}_{{\left(H\circ m\right)}^{U}}\left({v}_{i}^{s}\right)\ne {N}_{{\left(H\circ m\right)}^{U}}\left({v}_{j}^{t}\right)$ ( $1\le s\le {m}_{i}$ , $1\le t\le {m}_{j}$ ). If $i=j$ and ${m}_{i}=2$ , by the construction of the graph ${\left(H\circ m\right)}^{U}$ , we have $y\in {N}_{{\left(H\circ m\right)}^{U}}\left({v}_{i}^{1}\right)$ and $y\notin {N}_{{\left(H\circ m\right)}^{U}}\left({v}_{i}^{2}\right)$ ; $x\in {N}_{{\left(H\circ m\right)}^{U}}\left(y\right)$ and $x\notin {N}_{{\left(H\circ m\right)}^{U}}\left(v\right)$ for all $v\left(\ne y\right)\in V\left({\left(H\circ m\right)}^{U}\right)$ ; ${N}_{{\left(H\circ m\right)}^{U}}\left(x\right)=\left\{y\right\}$ and ${N}_{{\left(H\circ m\right)}^{U}}\left(v\right)\ne \left\{y\right\}$ for all $v\left(\ne x\right)\in V\left({\left(H\circ m\right)}^{U}\right)$ (because H has no isolated vertices). In a word, any two vertices in ${\left(H\circ m\right)}^{U}$ don’t have the same neighborhoods. Therefore, ${\left(H\circ m\right)}^{U}$ is a basic graph. $\square $

For the convenience of drawing, when ${m}_{i}=2$ , we use a hollow circle to indicate two vertices ${v}_{i}^{1}$ and ${v}_{i}^{2}$ , which have the same neighborhoods in $H\circ m$ , the vertex y is adjacent to ${v}_{i}^{1}$ but not adjacent to ${v}_{i}^{2}$ , and we use a black dot to indicate exactly one vertex. For example, the graph ${\left(H\circ m\right)}^{U}$ is depicted in Figure 4, where $H={C}_{5}$ , $V\left(H\right)=\left\{{v}_{1}\mathrm{,}{v}_{2}\mathrm{,}{v}_{3}\mathrm{,}{v}_{4}\mathrm{,}{v}_{5}\right\}$ , $m=\left(\mathrm{2,2,1,1,1}\right)$ and $U=\left\{{v}_{3}\mathrm{,}{v}_{4}\right\}$ .

Since there are multiple choices for the vector m and the subset U, there are also multiple choices for the graph ${\left(H\circ m\right)}^{U}$ , represented by $\mathcal{B}\left(H\right)$ as the set of all graphs ${\left(H\circ m\right)}^{U}$ .

Theorem 1. Let G be a graph without isolated vertices but with pendant vertices,

Figure 4. The graph ${\left({C}_{5}\circ m\right)}^{U}$ where $m=\left(2,2,1,1,1\right),U=\left\{{v}_{3},{v}_{4}\right\}$ .

$r\left(G\right)=7$ if and only if $G\in \mathcal{M}\left({\Omega}_{5}\right)$ , where ${\Omega}_{5}={\displaystyle {\cup}_{H\in {\Lambda}_{5}}}\mathcal{B}\left(H\right)$ , ${\Lambda}_{5}$ 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 $r\left(H\right)=5$ . 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, $H\in \mathcal{M}\left({\Lambda}_{5}\right)$ . Let $H=K\circ m$ , where $m=\left({m}_{1}\mathrm{,}{m}_{2}\mathrm{,}\cdots \mathrm{,}{m}_{n}\right)$ is a vector of positive integers, and $K\in {\Lambda}_{5}$ . If ${m}_{i}\ge 3$ , then there exists $s\mathrm{,}t\in \left\{\mathrm{1,2,}\cdots \mathrm{,}{m}_{i}\right\}$ such that ${N}_{G}\left({v}_{i}^{s}\right)={N}_{G}\left({v}_{i}^{t}\right)$ (since ${N}_{G}\left({v}_{i}^{s}\right)={N}_{H}\left({v}_{i}\right)$ or ${N}_{H}\left({v}_{i}\right)\cup \left\{y\right\}$ ). If ${m}_{i}=2$ , ${v}_{i}^{1}$ and ${v}_{i}^{2}$ are all adjacent to y or none are adjacent to y, then ${N}_{G}\left({v}_{i}^{1}\right)={N}_{G}\left({v}_{i}^{2}\right)$ , However, G is a basic graph, this is a contradiction. So ${m}_{i}\le 2$ , one and only one of the two vertices ${v}_{i}^{1}$ and ${v}_{i}^{2}$ is adjacent to y when ${m}_{i}=2$ . Therefore, we conclude that $G\in {\displaystyle {\cup}_{H\in {\Lambda}_{5}}}\mathcal{B}\left(H\right)$ . $\square $

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, ${K}_{2}$ is a basic extremal graph of rank 2, let’s say ${\Gamma}_{2}=\left\{{K}_{2}\right\}$ . ${K}_{3}$ is a basic extremal graph of rank 3, let’s say ${\Gamma}_{3}=\left\{{K}_{3}\right\}$ . ${H}_{6}\mathrm{,}{H}_{7}$ and ${H}_{8}$ (as shown in Figure 1) are basic extremal graphs of rank 4, let’s say ${\Gamma}_{4}=\left\{{H}_{6}\mathrm{,}{H}_{7}\mathrm{,}{H}_{8}\right\}$ . ${G}_{1}$ , ${G}_{2}$ , ${G}_{3}$ , ${G}_{11}$ , ${G}_{13}$ , ${G}_{17}$ , ${G}_{19}$ and ${G}_{24}$ (as shown in Figure 2) are basic extremal graphs of rank 5, let’s say

${\Gamma}_{5}=\left\{{G}_{1}\mathrm{,}{G}_{2}\mathrm{,}{G}_{3}\mathrm{,}{G}_{11}\mathrm{,}{G}_{13}\mathrm{,}{G}_{17}\mathrm{,}{G}_{19}\mathrm{,}{G}_{24}\right\}\mathrm{.}$

Obviously, in ${\Gamma}_{i}\left(i=2,3,4\right)$ , every graph is the vertex-induced subgraph of a certain graph in ${\Gamma}_{5}$ .

Let H be a a basic graph of rank 5, then all graphs in the set $\mathcal{B}\left(H\right)$ are basic graphs with pendant vertices and $r\left(G\right)=7$ . Let ${\left(H\circ m\right)}^{U}\in \mathcal{B}\left(H\right)$ , $m=\left({m}_{1},{m}_{2},\cdots ,{m}_{n}\right)$ , and every vector ${m}_{i}=1$ or 2 ( $i=1,2,\cdots ,n$ ). If some vectors ${m}_{i}\ne 2$ , then ${\left(H\circ m\right)}^{U}$ can’t be a basic extremal graph of rank 7, because it is a proper vertex-induced subgraph of ${\left(H\circ {m}^{\prime}\right)}^{\varnothing}$ , where ${m}^{\prime}=\left(\mathrm{2,2,}\cdots \mathrm{,2}\right)$ and $\varnothing $ is empty set. Particularly, let’s say ${\left(H\circ {m}^{\prime}\right)}^{\varnothing}=\mathbb{H}$ . Easy to prove, if H is a basic extremal graph of rank 5, then $\mathbb{H}$ is a basic extremal graph with pendant vertices and $r\left(G\right)=7$ . Hence we have the following theorem.

Theorem 2. Let G be a graph without isolated vertices but with pendant vertices, then $r\left(G\right)\le 7$ if and only if $G\in \mathcal{M}\left(\Delta \right)$ , where $\Delta $ is the set of all vertex-induced subgraphs of graphs in set $\Theta =\left\{\mathbb{H}\mathrm{|}H\in {\Gamma}_{5}\right\}$ .

Proof. By $H\in {\Gamma}_{5}$ , we know the rank of H is 5. By the definition of $\mathbb{H}$ 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 $\Delta $ . On the contrary, let G be a graph without isolated vertices but with pendant vertices, and $r\left(G\right)=k\le 7$ . Similar to the proof of theorem 1,

we have $G\in \mathcal{M}\left({\Omega}_{k-2}\right)$ , where ${\Omega}_{k-2}={\displaystyle {\cup}_{H\in {\Lambda}_{k-2}}}\mathcal{B}\left(H\right)$ . Because every graph in

${\Lambda}_{k-2}$ is the vertex-induced subgraph of a certain graph in ${\Gamma}_{k-2}$ , and every graph in ${\Gamma}_{k-2}\left(k=\mathrm{4,5,6,7}\right)$ is the vertex-induced subgraph of a certain graph in ${\Gamma}_{5}$ . On the other hand, every graph in $\mathcal{B}\left(H\right)$ is the vertex-induced subgraph of $\mathbb{H}$ . So $G\in \mathcal{M}\left(\Delta \right)$ . $\square $

4. Conclusion

By using the operation of multiplication of vertices, a characterization for graph G with pendant vertices and $r\left(G\right)=7$ is shown, and then a characterization for graph G with pendant vertices and $r\left(G\right)$ 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).

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.