Non-Singular Trees, Unicyclic Graphs and Bicyclic Graphs

Haicheng Ma^*, Danyang Li, Chengling Xie

Department of Mathematics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/am.2020.111001                

Abstract

We called graph G non-singular if adjacency matrix A (G) of G is non-singular. A connected graph with n vertices and n-1, n and n+1 edges are called the tree, the unicyclic graph and the bicyclic graph. Respectively, as we all know, each connected bicyclic graph must contain ∞(a,s,b) or θ(p,l,q) as the induced subgraph. In this paper, by using three graph transformations which do not change the singularity of the graph, the non-singular trees, unicyclic graphs and bicyclic graphs are obtained.

Keywords

Adjacency Matrix, Non-Singular, Rank, Nullity

1. Introduction

This paper considers only finite undirected simple graphs. Let G be a graph with order n, the matrix A is defined as the adjacency matrix of graph G, which is defined as follows: $A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$

$a_{ij}=(\begin{array}{cc}1& \text{if}i\sim j\text{,}\\ 0& \text{others}\text{.}\end{array}$

Obviously, $A\left(G\right)$ is a real symmetric matrix with diagonal elements of 0 and other elements of 0 or 1, its eigenvalues are real number. The eigenvalues of $A\left(G\right)$ are also said to be the eigenvalues of the graph G, collection n eigenvalues of G to form the spectrum of this graph. The number of nonzero eigenvalues and zero eigenvalues in the spectrum of the graph G are called the rant and nullity of the graph G, and denoted by $r\left(G\right)$ and $\eta \left(G\right)$, respectively, obviously $r\left(G\right)+\eta \left(G\right)=n$.

The chemist discovered, $\eta \left(G\right)=0$ is a necessary condition for the chemical stability of the molecules shown in the graph G [1] [2]. 1957, in [2], Collatz and Sinogowitz put forward a question that how to find out all singular graphs (equivalently, to show all the nonsingular graphs), namely, to describe all graphs with nullity are greater than zero, it was a very difficult problem only with some special results [3] [4] [5] [6] [7]. This has inspired a lot of researches on nullity of graph [8] - [14]. In this paper, by using three graph transformations which do not change the singularity, the non-singular trees, unicyclic graphs and bicyclic graphs are obtained. This method is different from previous.

A connected graph of order n, the graph respectively with size $n-1,n$ and $n+1$ are called the tree, the unicyclic graph and the bicyclic graph. As usual, $P_n$, $C_n$ and $K_n$ denoted respectively the path, the cycle and the complete graph on n vertices. $K_0$ denoted the null graph (namely, a graph without vertex). The graph obtained by bonding the two ends of the $P_s\left(s\ge 1\right)$ to one vertex on $C_a$ and $C_b$ is recorded as $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$, when $s=1$, $\infty \left(a\mathrm{,1,}b\right)$ denotes the graph obtained by bonding a vertex on $C_a$ with a vertex on $C_b$. The graphs obtained by bonding the starting vertices and the end vertices of the $P_l\mathrm{,}{P}_p$ and $P_q$ are respectively is recorded as $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$, where $\min \left\{p\mathrm{,}l\mathrm{,}q\right\}\ge 2$ and one of them at most is 2 (as shown in Figure 1). As everyone knows, each connected bicyclic graph must contain $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$ or $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$ as the induced subgraph. $G\cup H$ denotes the union graph of G and H. An edge relates a vertex of degree 1, then the vertex is called a pendant vertex, and the vertex adjacent to the pendant vertex is called the quasi-pendant vertex. The notation and terminology that are not described here are provided in [1].

2. Some Lemmas

Let $A\mathrm{,}B$ be two n-order real symmetric matrices, if there is an invertible matrix P of order n such that $P^{\text{T}}AP=B$, then we say that A is congruent to B, denoted by $A\simeq B$.

Lemma 2.1. [15] Let $A\mathrm{,}B$ be n-order real symmetric matrices of two congruent, then $r\left(A\right)=r\left(B\right)$, $\eta \left(A\right)=\eta \left(B\right)$.

Lemma 2.2. Let $G=G_1\cup G_2\cup \cdots \cup G_t$, where $G_i\left(i=1,2,\cdots ,t\right)$ are connected components of G. Then $\eta \left(G\right)={\displaystyle \underset{i=1}{\overset{t}{\sum }}\eta \left(G_i\right)}$. Equivalent G is non-singular if and only if every $G_i\left(i=1,2,\cdots ,t\right)$ is non-singular.

Lemma 2.3. [1] Let G have a pendant vertex, H is the graph obtained by deleting the pendant vertex from graph G and the quasi-pendant vertex adjacent to it, then $\eta \left(G\right)=\eta \left(H\right)$. Equivalently, G is non-singular if and only if every H is non-singular.

Lemma 2.4. [16] Let G be a graph containing path with four vertices of degree 2, let the graph H be obtained from G by replacing this path with an edge (as shown in Figure 2). Then $\eta \left(G\right)=\eta \left(H\right)$. Equivalently, G is non-singular if and only if every H is non-singular.

Lemma 2.5. [16] Let G be a graph containing two vertices and four edges of a cycle of length 4, positioned as shown in Figure 3. Let the graph H be obtained from G by removing this cycle. Then $\eta \left(G\right)=\eta \left(H\right)$. Equivalently G is non-singular if and only if every H is non-singular.

Figure 1. Graph $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$ and $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$.

Figure 2. Graph transformation (II) which does not change the singularity of the graph.

Figure 3. Graph transformation (III) which does not change the singularity of the graph.

We called the three graph transformations are given which does not change the singularity of the graph in Lemma 2.3, Lemma 2.4 and Lemma 2.5 are the graph transformation I, the graph transformation I and the graph transformation III, respectively.

We called the subgraph is elementary subgraph of G in which every component is $K_2$ or cycle. If a elementary subgraph of G contains all the vertices of G, then called this elementary subgraph that is the elementary spanning subgraph of G.

Lemma 2.6. [1] If G is a graph with n vertices and adjacency matrix is $A\left(G\right)$, then

$det\left(A\left(G\right)\right)={\left(-1\right)}^n{\displaystyle \underset{H\in \mathcal{H}}{\sum }}{\left(-1\right)}^{p\left(H\right)}{2}^{c\left(H\right)}\mathrm{,}$

where $\mathcal{H}$ is the set of elementary spanning subgraph of G, $p\left(H\right)$ denotes the number of components of H and $c\left(H\right)$ denotes the number of cycles in H.

3. Main Theorems

We agree $K_0$ is non-singular and denoted by ${\Omega }_1=\left\{K_0\right\}$.

Theorem 3.1. If T is a tree with order n, then T is non-singular if and only if T is changed to $K_0$ by a series of the graph transformation I.

Proof. As we all know, T is changed to $H=r{K}_1$ by a series of the graph transformation I, T is non-singular if and only if H is non-singular. When $r>0$, then H is singular, when $r=0$, then $H=K_0$ is non-singular. So T is non-singular if and only if T is changed to $K_0$ by a series of the graph transformation I.

Corollary 3.1. If a tree is non-singular if and only if T has a perfect matching.

Lemma 3.1. If a cycle $C_n$ is non-singular if and only if $4\nmid n$.

Proof. According Lemma 2.6, we can easily calculate $det\left(A\left(C_3\right)\right)=2$, $det\left(A\left(C_4\right)\right)=0$, $det\left(A\left(C_5\right)\right)=2$, $det\left(A\left(C_6\right)\right)=-4$. Let $n=4q+r$, $q\ge 0$, $3\le r\le 6$, $C_n$ is changed to $C_r$ by a series of the graph transformation II. Therefore $C_n$ is non-singular if and only if $C_r$ is non-singular and if and only if $4\nmid n$.

Denoted by ${\Omega }_2=\left\{C_3\mathrm{,}{C}_5\mathrm{,}{C}_6\right\}$.

Theorem 3.2. Let G is a unicyclic graph, then G is non-singular if and only if it is changed to $H\in {\Omega }_1\cup {\Omega }_2$ by a series of the graph transformation I and the graph transformation II.

Proof. As everyone knows, the unicyclic graph can always change to $r{K}_1$, $C_n$ or $r{K}_1\cup C_n$ through a series of the graph transformation I, and change to $H=r{K}_1$, $C_s$ or $r{K}_1\cup C_s\left(3\le s\le 6\right)$ through a series of the graph transformation II. By the Theorem 3.1 and the Lemma 3.1, unicyclic graph G is non-singular if and only if H is non-singular, and if and only if $H\in {\Omega }_1\cup {\Omega }_2$.

Denoted by

$\begin{array}{c}{\Gamma }_1=\{\infty \left(3,1,3\right),\infty \left(3,2,3\right),\infty \left(3,3,3\right),\infty \left(3,4,3\right),\infty \left(3,5,3\right),\infty \left(3,2,5\right),\\ \infty \left(3,4,5\right),\infty \left(3,1,6\right),\infty \left(3,2,6\right),\infty \left(3,3,6\right),\infty \left(3,4,6\right),\infty \left(3,5,6\right),\\ \infty \left(5,1,5\right),\infty \left(5,2,5\right),\infty \left(5,3,5\right),\infty \left(5,4,5\right),\infty \left(5,5,5\right),\infty \left(5,1,6\right),\\ \infty \left(5,2,6\right),\infty \left(5,3,6\right),\infty \left(5,4,6\right),\infty \left(5,5,6\right),\infty \left(6,2,6\right),\infty \left(6,4,6\right)\}.\end{array}$

Lemma 3.2. If $G=\infty \left(a\mathrm{,}s\mathrm{,}b\right)$, then G is non-singular if and only if G is changed to $H\in {\Gamma }_1$ by a series of the graph transformation II.

Proof. At first, we can prove graphs in the ${\Gamma }_1$ are non-singular. Taking $\infty \left(\mathrm{3,2,6}\right)$ as an example, it has a elementary spanning subgraph $C_6\cup C_3$ ; two $C_3\cup 3K_2$, so by Lemma 2.6, we can easily calculate $det\left(A\left(\infty \left(\mathrm{3,2,6}\right)\right)\right)={\left(-1\right)}^9\left[{\left(-1\right)}^2{2}^2+{\left(-1\right)}^{4}2\times 2\right]=-8$. The others are similar, so we have following:

$\begin{array}{l}det\left(A\left(\infty \left(\mathrm{3,1,3}\right)\right)\right)=-4,det\left(A\left(\infty \left(\mathrm{3,2,3}\right)\right)\right)=3,det\left(A\left(\infty \left(\mathrm{3,3,3}\right)\right)\right)=4,\\ det\left(A\left(\infty \left(\mathrm{3,4,3}\right)\right)\right)=-3,det\left(A\left(\infty \left(\mathrm{3,5,3}\right)\right)\right)=-4,det\left(A\left(\infty \left(\mathrm{3,2,5}\right)\right)\right)=5,\\ det\left(A\left(\infty \left(\mathrm{3,4,5}\right)\right)\right)=-5,det\left(A\left(\infty \left(\mathrm{3,1,6}\right)\right)\right)=4,det\left(A\left(\infty \left(\mathrm{3,2,6}\right)\right)\right)=-8,\\ det\left(A\left(\infty \left(\mathrm{3,3,6}\right)\right)\right)=-4,det\left(A\left(\infty \left(\mathrm{3,4,6}\right)\right)\right)=8,det\left(A\left(\infty \left(\mathrm{3,5,6}\right)\right)\right)=4,\end{array}$

$\begin{array}{l}det\left(A\left(\infty \left(5,1,5\right)\right)\right)=4,det\left(A\left(\infty \left(5,2,5\right)\right)\right)=3,det\left(A\left(\infty \left(5,3,5\right)\right)\right)=-2,\\ det\left(A\left(\infty \left(5,4,5\right)\right)\right)=-3,det\left(A\left(\infty \left(5,5,5\right)\right)\right)=4,det\left(A\left(\infty \left(5,1,6\right)\right)\right)=-4,\\ det\left(A\left(\infty \left(5,2,6\right)\right)\right)=-8,det\left(A\left(\infty \left(5,3,6\right)\right)\right)=4,det\left(A\left(\infty \left(5,4,6\right)\right)\right)=8,\\ det\left(A\left(\infty \left(5,5,6\right)\right)\right)=-4,det\left(A\left(\infty \left(6,2,6\right)\right)\right)=16,det\left(A\left(\infty \left(6,4,6\right)\right)\right)=-16.\end{array}$

Denoted by

$\begin{array}{c}{\Delta }_1=\{\infty \left(3,1,4\right),\infty \left(3,2,4\right),\infty \left(3,3,4\right),\infty \left(3,4,4\right),\infty \left(3,5,4\right),\infty \left(3,1,5\right),\infty \left(3,3,5\right),\\ \infty \left(4,1,4\right),\infty \left(4,2,4\right),\infty \left(4,3,4\right),\infty \left(4,4,4\right),\infty \left(4,5,4\right),\infty \left(4,1,5\right),\infty \left(4,2,5\right),\\ \infty \left(4,3,5\right),\infty \left(4,4,5\right),\infty \left(4,5,5\right),\infty \left(4,1,6\right),\infty \left(4,2,6\right),\infty \left(4,3,6\right),\infty \left(4,4,6\right),\\ \infty \left(4,5,6\right),\infty \left(6,1,6\right),\infty \left(6,3,6\right),\infty \left(6,5,6\right)\}.\end{array}$

Then we prove graphs in the ${\Delta }_1$ are singular. For graph $\infty \left(\mathrm{4,}s\mathrm{,}b\right)$ or $\infty \left(a\mathrm{,}s\mathrm{,4}\right)$, we use the graph transformation III, will get a graph which contains $K_1$, yet $K_1$ provides a zero eigenvalue, so these kind of graphs are singular.

For the others, we have following:

$\begin{array}{l}det\left(A\left(\infty \left(\mathrm{3,1,5}\right)\right)\right)=0,det\left(A\left(\infty \left(\mathrm{3,3},5\right)\right)\right)=0,\\ det\left(A\left(\infty \left(\mathrm{6,1,6}\right)\right)\right)=0,det\left(A\left(\infty \left(\mathrm{6,3,6}\right)\right)\right)=0,det\left(A\left(\infty \left(\mathrm{6,5,6}\right)\right)\right)=0.\end{array}$

At last, let $a\ge \mathrm{3,}b\ge \mathrm{3,}s\ge 1$, and $a=4i+a^{\prime }\left(3\le a^{\prime }\le 6\right)$, $b=4j+b^{\prime }\left(3\le b^{\prime }\le 6\right)$, $s=4k+a^{\prime }\left(1\le s^{\prime }\le 5\right)$, for graph $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$, we repeatedly use the graph transformation II, will get graph $\infty \left(a^{\prime }\mathrm{,}{s}^{\prime }\mathrm{,}{b}^{\prime }\right)\in {\Gamma }_1\cup {\Delta }_1$. So $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$ is non-singular if and only if $\infty \left(a^{\prime }\mathrm{,}{s}^{\prime }\mathrm{,}{b}^{\prime }\right)$ is non-singular, if and only if $\infty \left(a^{\prime }\mathrm{,}{s}^{\prime }\mathrm{,}{b}^{\prime }\right)\in {\Gamma }_1$.

Denoted by

$\begin{array}{c}{\Gamma }_2=\{\theta \left(\mathrm{2,3,5}\right)\mathrm{,}\theta \left(\mathrm{2,3,6}\right)\mathrm{,}\theta \left(\mathrm{2,4,4}\right)\mathrm{,}\theta \left(\mathrm{2,4,6}\right)\mathrm{,}\theta \left(\mathrm{2,5,6}\right)\mathrm{,}\\ \theta \left(\mathrm{2,6,6}\right)\mathrm{,}\theta \left(\mathrm{3,4,4}\right)\mathrm{,}\theta \left(\mathrm{3,4,5}\right)\mathrm{,}\theta \left(\mathrm{4,4,4}\right)\mathrm{,}\theta \left(\mathrm{4,4,5}\right)\}\end{array}$

Lemma 3.3. Let $G=\theta \left(p\mathrm{,}l\mathrm{,}q\right)$, then G is non-singular if and only if G is changed to $H\in {\Gamma }_2$ through a series of the graph transformation II.

Proof. First of all, we can prove that the graphs in the ${\Gamma }_2$ are non-singular. Taking $\theta \left(\mathrm{2,3,5}\right)$ as an example, it has a elementary spanning subgraph $C_6$ ; two $3K_2$, so by Lemma 2.6, we can calculate $det\left(A\left(\theta \left(\mathrm{2,3,5}\right)\right)\right)={\left(-1\right)}^6\left[{\left(-1\right)}^{1}2+{\left(-1\right)}^3\times 2\right]=-4$. The others are similar, so we have following:

$\begin{array}{l}det\left(A\left(\infty \left(2,3,6\right)\right)\right)=4,det\left(A\left(\infty \left(2,4,4\right)\right)\right)=-1,det\left(A\left(\infty \left(2,4,6\right)\right)\right)=1,\\ det\left(A\left(\infty \left(2,5,6\right)\right)\right)=4,det\left(A\left(\infty \left(2,6,6\right)\right)\right)=-9,det\left(A\left(\infty \left(\mathrm{3,4,4}\right)\right)\right)=-4,\\ det\left(A\left(\infty \left(3,4,5\right)\right)\right)=4,det\left(A\left(\infty \left(4,4,4\right)\right)\right)=9,det\left(A\left(\infty \left(4,4,5\right)\right)\right)=-4.\end{array}$

Denoted by

$\begin{array}{c}{\Delta }_2=\{\theta \left(2,3,3\right),\theta \left(2,3,4\right),\theta \left(2,4,5\right),\theta \left(2,5,5\right),\theta \left(3,3,3\right),\\ \theta \left(3,3,4\right),\theta \left(3,3,5\right),\theta \left(3,5,5\right),\theta \left(4,5,5\right),\theta \left(5,5,5\right)\}.\end{array}$

We can easily prove that graphs in the ${\Delta }_2$ are singular.

At last, let $p\ge \mathrm{2,}l\ge \mathrm{3,}q\ge 3$, and $p=4i+p^{\prime }\left(2\le p^{\prime }\le 5\right)$, $l=4j+l^{\prime }\left(2\le l^{\prime }\le 5\right)$, $q=4k+q^{\prime }\left(2\le q^{\prime }\le 5\right)$, for graph $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$, we repeatedly use the graph transformation II, will get graph $\theta \left(p^{\prime }\mathrm{,}{l}^{\prime }\mathrm{,}{q}^{\prime }\right)\in {\Gamma }_2\cup {\Delta }_2$. So, $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$ is non-singular if and only if $\theta \left(p^{\prime }\mathrm{,}{l}^{\prime }\mathrm{,}{q}^{\prime }\right)$ is non-singular, if and only if $\theta \left(p^{\prime }\mathrm{,}{l}^{\prime }\mathrm{,}{q}^{\prime }\right)\in {\Gamma }_2$.

Denoted by ${\Omega }_3={\Gamma }_1\cup {\Gamma }_2$.

Theorem 3.3. Let G be a bicyclic graph, then G is non-singular if and only if G is changed to $H\in {\Omega }_1\cup {\Omega }_2\cup {\Omega }_3$ by a series of the graph transformation I and the graph transformation II.

Proof. As everyone knows, the bicyclic graph can always change to $r{K}_1$, $C_n$, $\infty \left(a\mathrm{,}s\mathrm{,}b\right)$, $\theta \left(p\mathrm{,}l\mathrm{,}q\right)$, $r{K}_1\cup C_n$, $r{K}_1\cup \infty \left(a\mathrm{,}s\mathrm{,}b\right)$ or $r{K}_1\cup \theta \left(p\mathrm{,}l\mathrm{,}q\right)$ through a series of the graph transformation I, and change to $H=r{K}_1\cup H^{\prime }$, $H^{\prime }\in \left\{K_0\mathrm{,}{C}_r\left(3\le r\le 6\right)\right\}\cup {\Gamma }_1\cup {\Delta }_1\cup {\Gamma }_2\cup {\Delta }_2$ through a series of the graph transformation II. By the Lemma 2.3 and the Lemma 2.4, bicyclic graph G is non-singular if and only if H is non-singular, and by the Theorem 3.1, Theorem 3.2, Lemma 3.2 and the Lemma 3.3, H is non-singular if and only if $H=H^{\prime }\in {\Omega }_1\cup {\Omega }_2\cup {\Omega }_3$.

4. Conclusion

By using three graph transformations which do not change the singularity of the graph, we found the non-singular trees, unicyclic graphs and bicyclic graphs. After writing this paper, I am very inspired; therefore, I want to do further research on the rank of graphs of more complex structures and so on.

Acknowledgements

This work is supported by National Natural Science Foundation of China (11561056, 11661066), National 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.

References

[1]	Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.
[2]	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
[3]	Sciriha, I. and Fowler, P.W. (2008) On Nut and Core Singular Fullerenes. Discrete Mathematics, 308, 267-276. https://doi.org/10.1016/j.disc.2006.11.040
[4]	Brown, M., Kennedy, J.W. and Servatius, B. (1993) Graph Singularity. Graph Theory Notes of New York, 25, 23-32.
[5]	Sciriha, I. (1998) On Singular Line Graphs of Trees. Congressus Numerantium, 135, 73-91.
[6]	Sciriha, I. (2007) A Characterization of Singular Graphs. The Electronic Journal of Linear Algebra, 16, 451-462. https://doi.org/10.13001/1081-3810.1215
[7]	Ashraf, F. and Bamdad, H. (2008) A Note on Graphs with Zero Nullity. MATCH Communications in Mathematical and in Computer Chemistry, 60, 15-19.
[8]	Fan, Y.Z. and Qian, K.S. (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
[9]	Guo, J.M., Yan, W. and Yeh, Y.N. (2009) On the Nullity and the Matching Number of Unicyclic Graphs. Linear Algebra and Its Applications, 431, 1293-1301. https://doi.org/10.1016/j.laa.2009.04.026
[10]	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
[11]	Hu, S., Tan, X. and Liu, B. (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
[12]	Chang, A. (2006) On the Trees with Maximum Nullity. MATCH Communications in Mathematical and in Computer Chemistry, 56, 501-508.
[13]	Omidi, G.R. (2009) On the Nullity of Bipartite Graphs. Graphs and Combinatorics, 25, 111-114. https://doi.org/10.1007/s00373-008-0825-5
[14]	Cheng, B. and Liu, B. (2007) On the Nullity of Graphs. The Electronic Journal of Linear Algebra, 16, 60-67. https://doi.org/10.13001/1081-3810.1182
[15]	Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon Inc., Boston.
[16]	Ma, H., Yang, W. and Li, S. (2013) Positive and Negative Inertia Index of a Graph. Linear Algebra and Its Applications, 438, 331-341. https://doi.org/10.1016/j.laa.2012.07.014