**Applied Mathematics**

Vol.05 No.10(2014), Article ID:46894,9 pages

10.4236/am.2014.510156

A Note on the Nullity of unicyclic graphs

Shengbiao Hu

Department of Mathematics, Qinghai Nationalities University, Xining, China

Email: shengbiaohu@aliyun.com

Copyright © 2014 by author and Scientific Research Publishing Inc.

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

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

Received 17 March 2014; revised 18 April 2014; accepted 26 April 2014

ABSTRACT

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper we show the expression of the nullity and nullity set of unicyclic graphs with n vertices and girth r, and characterize the unicyclic graphs with extremal nullity.

**Keywords:**

Eigenvalues (of Graphs), Nullity, Unicyclicgraphs

1. Introduction

Let be a simple undirected graph with n vertices. The disjoint union of two graphs G_{1} and G_{2} is denoted by. The null graph of order n is the graph with n vertices and no edges. As usual, the star, path, cycle and the complete graph of order n are denoted by S_{n}, P_{n}, C_{n} and K_{n}, respectively. An isolated vertex is sometimes denoted by K_{1}.

Let A(G) be the adjacency matrix of G. The eigenvalues of A(G) are said to be the eigenvalues of G, and to form the spectrum of this graph. The number of zero eigenvalues in the spectrum of the graph G is

called its nullity and is denoted by η(G). Let r(G) be the rank of A(G). Clearly,.

A graph is said to be singular (nonsingular) if its adjacency matrix A(G) is a singular (nonsingular) matrix.

In [1] , L. Collatz and U. Sinogowitz first posed the problem of characterizing all graphs which satisfying. This question is of great interest in chemistry, because, as has been shown in [2] , for a bipartite graph

G (corresponding to an alternant hydrocarbon), if, then it indicates the molecule which such a graph

represents is unstable. The nullity of a graph is also important in mathematics, since it is related to the singularity of A(G). The problem has not yet been solved completely. Some results on trees and it’s line graphs, bipartite graphs, unicyclic graphs, bicyclic graphs and tricyclic graphs are known (see [3] - [14] ). For details and further references we see [15] [16] .

A unicyclic graph is a simple connected graph in which the number of edges equals the number of vertices.

The length of the shortest cycle in a graph G is called the girth of G, denoted by g(G). If G is a unicyclic graph, then the girth of G is the length of the only cycle in G.

Let U_{n} be the set of all unicyclic graph with n vertices and let U(n, r) be the set of all unicyclic graphs with n vertices and girth r. A subset N of {0, 1, 2, ..., n} is said to be the nullity set of U(n, r) provided that for any kÎN, there exists at least one graph such that, and no k Ï N satisfies this property.

A matching of G is a set of independent edges of G, a maximal matching is a matching with maximum possible number of edges. The collection of all maximal matching is denoted by M(G), for any, the size of M, i.e., the maximum number of independent edges in G, is denoted by. If n is even and, then we call the maximal matching a perfect matching of G, shot for PM.

It is difficult to give an expression of the nullity of a graph, so many papers give that the upper bound of the nullity of some specific graphs and characterized the extremal graphs attaining the upper bound (see [6] [9] [11] [12] [14] [17] ). For the trees we know the following concise formula:

Theorem 1.1 [3] If t is a tree with n vertices and m is the size of its maximal matchings, then its nullity is equal to.

Theorem 1.1 implies to if and only if T is a PM-tree.

In this paper we show the expression of the nullity and nullity set of unicyclic graphs with n vertices and girth r, and characterize the unicyclic graphs with extremal nullity. For terminology and notation not defined here we refer to [3] .

2. Some Lemmas

The following lemmas are needed, Lemmas 2.1 and Lemma 2.3 are clear.

Lemma 2.1 Let H be an induced subgraph of G. Then,

Lemma 2.2 Let H be an induced subgraph of G. Then.

Proof..

Lemma 2.3 Let,_{ }then,

where are connected components of G.

Lemma 2.4 [14]

Let, if r = n, then by Lemma 2.4 we have

Lemma 2.5

So we discuss that r < n in the following unicyclics. Let U_{0}(n, r) be the set of all unicyclic graphs with n vertices and girth r and r < n, let U_{0,1}(n, r) be the subset of U_{0}(n, r) with odd girth r and let U_{0,2}(n, r) be the subset

of U_{0}(n, r) with even girth r, clearly and.

Lemma 2.6 [3] For a graph G containing a vertex of degree 1, if the induced subgraph H (of G) is obtained by deleting this vertex together with the vertex adjacent to it, then the relation holds.

The characteristic polynomial of graph G is denoted by

(1)

Lemma 2.7 [3] Let. Then the coefficient of x^{n-i} is

. (2)

where the sum is over all subgraphs H of G consisting of disjoint edges and cycles, and having i vertices. If H is such a subgraph then k(H) is the number of components in it and c(H) is the number of cycles.

Let in (2), then, where H is spanning subgraphs of G consisting of disjoint

edges and cycles.

3. Main Results

In [18] , Ashraf and Bamdad considered the opposite problem: which graphs have nullity zero? Clearly, for a graph G, if and only if and if and only if in (1). So by (1) we have following theorem, that is

Theorem 3.1 For a graph G,

1) if and only if,

2) if and only if.

where the sum is over all spanning subgraphs H of G consisting of disjoint edges and cycles.

Proof. By (1) it is clear.

By (1) we know also that if and only if there exist, such that and

(Note that and). So we have

Corollary 3.1 For a graph G, if and only if for

and for in (2).

Let U be a unicyclic graph with girth r, Let H be a subgraphs of U consisting of disjoint edges and cycles with maximum possible number of vertices. Let H be the collection of all H. Since U is unicyclic graph, then H have

two types: and m(U)P_{2}, where C_{r} is induced subgraph of U and mP_{2} is disjoint union of

m edges P_{2}. Let and, clearly and

. If, then.

Since U doesn’t contains a subgraph G_{1} consisting of disjoint edges and cycles, such that

, hence for,

. So we have

Corollary 3.2 Let U be a unicyclic graph with girth r, then if and only if

, where.

Theorem 3.2 Let, then

1) there exist, for any r/2 edges in M, such that they not all belong to E(C_{r});

2) for any, there exist r/2 edges in M, such that they all belong to E(C_{r}).

Where C_{r} is induced subgraph of U.

Proof. Let and let C_{r} be an induced subgraph of U. By Corollary 2.2, we only need to discuss

that whether equals zero. We give a sign for the edges of C_{r}, in nature order.

Case 1.. Since is odd and

is even, , hence either or. If,

then and. Since for all, they have the same number of component, hence

, where. If, then

and. Similarly, , where. Thus

.

Case 2..

Subcase 2.1 There exist, where. In this case, the

and

, where the in H_{0}, H_{1} and

H_{2} are same, and we call H_{1} and H_{2} are conjugate subgraph of H_{0}. Since r/2 is odd, hence for any HÎH, the

number of component of H have the same odevity, hence, where.

Subcase 2.2 There doesn’t exist. In this case, since all and they have the same edges,

hence, where. So.

Case 3. and there exist, for any r/2 edges in M, such that they not all belong to E(C_{r}).

Subcase 3.1 There exist H_{0}ÎH_{1}, where. In this case, the

and

. Let. For,

we have

.

Since we know that there exist, for any r/2 edges in M, such that they not all belong to E(C_{r}),

hence we assume that and for any r/2 edges in H_{3}, such that they not all belong to

E(C_{r}). Except H_{3}, if there exist others (i ≥ 4) and for any r/2 edges in H_{i} (i ≥ 4), such that they not all belong to E(C_{r}), then we have

and, so.

Subcase 3.2 There aren’t exist. In this case, similar to Subcase 2.2 of Case 2, we have.

Case 4. r ≡ 0(mod 4) and for any, there exist r/2 edges in M, such that they all belong to E(C_{r}).

In this case, for any, let, where

is independent edges in C_{r.} For the same with H_{1}, let

and, where

is also independent edges in C_{r}, then and. In fact, in this case for any one, there

exist a conjugate graph of H′, such that, where H′ and H′′ are conjugate subgraphs of H,

that is and. Similarly, for any one, it corres-

ponding two conjugate subgraphs. So

,

where. Since if, thus we consider the subgraph

H of U consisting of disjoint edges and cycles, and having m(U) ? 1 edges. Clearly there exist a

(m(U) ? 1)-matching, such that there exist r/2 − 1 edges belong in E(C_{r}) and edges belong in

. Similar to Case 3, , where. So

.

Let C_{r} be a cycle and let P_{n}_{−}_{r} be a path. Suppose that v is a vertex of C_{r} and u is a pendant vertex of P_{n}_{−}_{r}. Joining v and u by an edge, the resulting graph (Figure 1) is denoted by U(r, n ? r).

Corollary 3.3 Let, then

Proof. Since, hence U contains an induced subgraph U(r, 1) (see Figure 1).

Case 1.. In this case, by Theorem 2.2 we have

, by Lemma 2.2 we

have.

Case 2.. In this case, if, by Theorem 2.2 we have

. If, then there exist, such that the pen-

dant edge belong to M, that is for any r/2 edges in M, it not all belong to E(C_{r}), so

, by Lemma 2.2 we have.

Let if r is odd and letif r is even in Corollary 2.3, and combine to Lemma 2.7 we have

Corollary 3.4 [18] For any (n ≥ 5),.

Corollary 3.5 Let, then if and only if n is even and U contains PM or n is odd and contains PM.

Proof. Let, where r is odd.

“⇒” If, then by Theorem 2.2 we have.

Case 1. If n is even, then, U contains PM.

Case 2. If n is odd, then, , contains PM.

“⇐”

Case 1. If n is even and U contains PM, then, by Theorem

2.2, η(U) = 0.

Case 2. If n is odd and contains PM, then

, by Theorem 2.2,.

Corollary 3.6 Let, then if and only if and U contains PM or

and U contains PM, and for any r/2 edges in the PM, such that they not all belong to E(C_{r}).

Figure 1. The unicyclic graph U(r, n − r) and U(r, 1).

Proof. Let, where r is even.

“⇒” If, then by theorem 2.2 we have or. If

, then, a contradiction. So we have, U contains PM. Since r

is even, hence or. If, then there exist PM, for any r/2 edges in the

PM, such that they not all belong to E(C_{r}). Otherwise, by Theorem 2.2 we have, a contradiction.

“⇐”

Case 1. If and U contains PM, then by Theorem 2.2 we have.

Case 2. If and U contains PM, and for any r/2 edges in the PM, such that it not all belong to E(C_{r}), then by Theorem 2.2 we have.

An edge belonging to a matching of a graph G is said to cover its two end-vertices. A vertex v is said to be perfectly covered (PC) if it is covered in all maximal matching of G [7] .

Any vertex adjacent to a pendent vertex is a PC-vertex. However, there may be exist PC-vertices adjacent to no pendent vertex. For instance, the central vertex in the path on an odd number of vertices is PC.

Let be the PC-vertices of C_{r}. Let be a graph is obtained from C_{r}, by adding r_{i}

pendant edges in the PC-vertex of C_{r}, respectively. Where

. The degree of PC-vertices of needn’t equality, even for some PC-vertices, no pendant

vertex joint to the PC-vertex, but the sum of number of all pendant vertices is n ? r. For r = 5 and 6, an and

see Figure 2, the PC-vertices are indicated by numbers 1, 2, 3.

Let be the set of all, where r is odd and let be the set of all, where r is even.

Clearly and. For any (i = 1, 2), the PC-vertices of

C_{r} is also the PC-vertices of U, where C_{r} is inducted subgraph of U.

Let d(v, G) denote the distance from a vertex v to the graph G, if vÎV(G), then.

Corollary 3.7 Let, then if and only if.

Proof. Since, hence r is odd.

“⇒” Let, if, by Theorem 2.1 we have

. Since r is odd, hence, , so for any

pendant v of U,. Otherwise, , a contradiction. If there exist at least one pendant

vertex v in U, such that, then there exist at least one independent edge in, so

, , a contradiction.

So for any pendant vertex of U,. Since there exist (r+1)/2 PC-vertices in C_{r}, if there exist pendant

edges for every vertices of C_{r} in U, then, a contradic-

tion. Hence there exist pendant edges for part of vertices of C_{r} in U. If there exist (r+1)/2 + 1 vertices in C_{r} such

that every vertex have pendant edges, then, a con-

tradiction. So there exist at most (r+1)/2 vertices, such that every vertex have pendant edges, that is all pendant

vertices of U joint to at most (r+1)/2 vertices in C_{r}. In the neighbor vertices of all pendant vertices of U, if there

exist (r?1)/2 PC-vertices and one non PC-vertex of C_{r}, then

, a contradiction.

Thus all pendant vertices of U are joint to the PC-vertices of C_{r}, thus.

“⇐” Let (see Figure 2), since r is odd, and, hence

, by Theorem 2.1, we have

Figure 2. An and an, its PC-vertices are indicated by numbers 1, 2, 3..

.

Let u be a vertex of C_{r}, and let v be a k-degree vertex of K_{1,k+1}. Joining u and v by a path P_{l}, the resulting graph is denoted by U(r, l, k + 1), where. When l = 2, we get U(r, 2, k + 1) (Figure 3).

For convenience, we call the star in U(r, 2, k + 1) is pendant star. Let U′(r, l, k) be a unicyclic graph come from U(r, l, k + 1), by removing a pendant edge and adding it to another vertex of C_{r}, where r + l + k = n (See Figure 4).

Corollary 3.8 Let, then if and only if or

and

Proof. Since, hence r is even.

“⇒” Let, if, by Theorem 2.2 we have or.

Case 1.. In this case, since r is even, hence for any pendant v of U,. Otherwise,

, a contradiction. For an edge, If u and v both have at lest one pendant edge in U,

respectively. Then, a contradiction. So all pendant vertices of U join to some PC-vertices of U,

thus.

Case 2.. In this case, since r is even, hence for any one pendant v of U,

. Otherwise, , a contradiction.

Subcase 2.1. There exist vÎU, such that. In this case, U(n, 3) (see Figure 1) is an induced sub-

graph of U, then there exist, such that the pendant edge belong to M, so for any r/2 edges in

M, it not all belong to E(C_{r}), by Theorem 2.1 we have, by Lemma 2.2,

, a contradiction.

Subcase 2.2. There exist vÎU, such that. In this case, U(r, 2, k +1) (see Figure 3, specially take k=0) is an induced subgraph of U, and only one vertex of U have only one pendant star. Otherwise, a contradiction. If there exist at lest one pendant edge in other one vertex of C_{r}, the resulting graph is denoted by U′(r, 2, k) (see Figure 4). Since there exist, such that the two inde-

pendent pendant edges in (U′(r,2,k)) belong to M, we know that, hence for any r/2

edges in M, they not all belong to E(C_{r}), by Lemma 2.2 and Theorem 2.2 we have

, a contradiction. So (see Figure 3).

If, by Theorem 2.2 we have, a contradic-

tion. So and.

“⇐” Case 1. Let (see Figure 2), since r is even, hence. If, then by

Theorem 2.1 we have. If, since r < n, hence U contains a induced

subgraph U(r, 1) (see Figure 1), for a, let the pendant edge of U(r, 1) belong to the M, then

the r/2 edges in M, not all belong to E(C_{r}), by Theorem 2.2 we have.

Case 2. Let and, then. Since for any

Figure 3. The unicyclic graphs U(r, l, k) and U(r, 2, k).

Figure 4. The unicyclic graphs U′(r, l, k) and U′(r, 2, k).

Figure 5. The unicyclic graph U(r, 1, k + 1).

, there exist r/2 edges in M, such that they all belong to E(C_{r}), by Theorem 2.1 we have

.

Let l = 1 in U(r, l, k+1) (Figure 3), we get the following graph U(r, 1, k +1) (Figure 5).

Theorem 3.3 The nullity set of U_{0,1}(n, r) is {0, 1, 2, ..., n-r-1}.

Proof. By Corollary 2.3, we only need to show that for each, there exist a unicyclic

graph such that, where r is odd.

Case 1.. Let (see Figure 1). If, using Lemma 2.6, after (n − r)/2 steps,

we get C_{r}, by Lemma 2.6 and 2.5 we have. If, using Lemma 2.6, af-

ter (n − 2)/2 steps, we get a P_{2}, by Lemmas 2.6 we have.

Case 2.. Let (see Figure 5), where, using Lemma 2.5, after

(r+1)/2 steps, we get kK_{1}, by Lemmas 2.3 we have.

Case 3.. Let (see Figure 3), where. If, Us-

ing Lemma 2.6, after l/2 steps, we get, by Lemmas 2.3 and 2.5 we have

. Similarly, If, we have

.

Theorem 3.4 The nullity set of U_{0,2}(n, r) is.

Proof. Similar to Theorem 2.3, if, we consider the graph U(r, l, k) with k pendants (see Figure 3

), where. If, we consider the graph U′(r, l, k) with k pendants (see Figure 4),

where.

If we take in Theorem 2.3 and in Theorem 2.4, then we have the following Corollary:

Corollary 3.9 [18] The nullity set of U_{n} is.

Acknowledgements

This work is supported by the Natural Science Foundation of Qinghai Province (Grant No. 2011-Z-911).

Cite this paper

Shengbiao Hu, (2014) A Note on the Nullity of Unicyclic Graphs. *Applied Mathematics*,**05**,1623-1631. doi: 10.4236/am.2014.510156

References

- 1. Von Collatz, L. and Sinogowitz, U. (1957) Spektren Endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 21, 63-77. http://dx.doi.org/10.1007/BF02941924
- 2. Longuet-Higgins, H.C. (1950) Resonance Structures and MO in Unsaturated Hydrocarbons. The Journal of Chemical Physics, 18, 265-274. http://dx.doi.org/10.1063/1.1747618
- 3. Cvetkovic, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Academic Press, New York.
- 4. Cvetkovic, D.M. 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.M., Gutman, I. and Trinajstic, N. (1972) Graph Theory and Molecular Orbitals, II. Croatica Chemica Acta, 44, 365-374.
- 6. Fiorini, S., Gutman, I. and Sciriha, I. (2005) Trees with Maximum Nullity. Linear Algebra and Its Applications, 397, 245-251. http://dx.doi.org/10.1016/j.laa.2004.10.024
- 7. Sciriha, I. (1998) On Singular Line Graphs of Trees. Congressus Numeratium, 135, 73-91.
- 8. Sciriha, I. and Gutman, I. (2001) On the Nullity of Line Graphs of Trees. Discrete Mathematics, 232, 35-45.
- 9. Hu, S., Tan, X. and Liu, B. (2008) On the Nullity of Bicyclic Graphs. Linear Algebra and Its Applications, 429, 1387-1391. http://dx.doi.org/10.1016/j.laa.2007.12.007
- 10. Li, J., Chang, A. and Shiu, W.C. (2008) On the Nullity of Bicyclic Graphs. Match Communications in Mathematical and in Computer Chemistry, 60, 21-36.
- 11. Li, S. (2008) On the Nullity of Graphs with Pendent Vertices. Linear Algebra and Its Applications, 429, 1619-1628. http://dx.doi.org/10.1016/j.laa.2008.04.037
- 12. Li, W. and Chang, A. (2006) On the Trees with Maximum Nullity. Match Communications in Mathematical and in Computer Chemistry, 56, 501-508.
- 13. Nath, M. and Sarma, B.K. (2007) On the Null-Spaces of Acyclic and Unicyclic Singular Graphs. Linear Algebra and Its Applications, 427, 42-54. http://dx.doi.org/10.1016/j.laa.2007.06.017
- 14. Tan, X.Z. and Liu, B.L. (2005) On the Nullity of Unicyclic Graphs. Linear Algebra and Its Applications, 408, 212-220. http://dx.doi.org/10.1016/j.laa.2005.06.012
- 15. Sciriha, I. (1998) On the Contruction of Graphs of Nullity One. Discrete Mathematics, 181, 193-211. http://dx.doi.org/10.1016/S0012-365X(97)00036-8
- 16. Sciriha, I. (1999) On the Rank of Graphs. In: Alavi, Y., Lick, D.R. and Schwenk, A., Eds., Combinatorics, Graph Theory and Algrithms, (2), New Issue Press, Western Michigan University, Kalamazoo, 769-778.
- 17. Cheng, B. and Liu, B. (2007) On the Nullity of Graphs. Electronic Journal of Linear Algebra, 16, 60-67.
- 18. Ashraf, F. and Bamdad, H. (2008) A Note on Graphs with Zero Nullity. Match Communications in Mathematical and in Computer Chemistry, 60, 15-19.