﻿ A Note on the Nullity of Unicyclic Graphs

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   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 G1 and G2 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 Sn, Pn, Cn and Kn, respectively. An isolated vertex is sometimes denoted by K1.

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  , 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  , 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  -  ). For details and further references we see   .

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 Un 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       ). For the trees we know the following concise formula:

Theorem 1.1  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  .

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 

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 U0(n, r) be the set of all unicyclic graphs with n vertices and girth r and r < n, let U0,1(n, r) be the subset of U0(n, r) with odd girth r and let U0,2(n, r) be the subset

of U0(n, r) with even girth r, clearly and.

Lemma 2.6  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  Let. Then the coefficient of xn-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  , 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)P2, where Cr is induced subgraph of U and mP2 is disjoint union of

m edges P2. Let and, clearly and

. If, then.

Since U doesn’t contains a subgraph G1 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(Cr);

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

Where Cr is induced subgraph of U.

Proof. Let and let Cr 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 Cr, 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 H0, H1 and

H2 are same, and we call H1 and H2 are conjugate subgraph of H0. 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(Cr).

Subcase 3.1 There exist H0ÎH1, 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(Cr),

hence we assume that and for any r/2 edges in H3, such that they not all belong to

E(Cr). Except H3, if there exist others (i ≥ 4) and for any r/2 edges in Hi (i ≥ 4), such that they not all belong to E(Cr), 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(Cr).

In this case, for any, let, where

is independent edges in Cr. For the same with H1, let

and, where

is also independent edges in Cr, 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(Cr) and edges belong in

. Similar to Case 3, , where. So

.

Let Cr be a cycle and let Pnr be a path. Suppose that v is a vertex of Cr and u is a pendant vertex of Pnr. 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(Cr), 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  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(Cr).

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(Cr). 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(Cr), 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  .

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 Cr. Let be a graph is obtained from Cr, by adding ri

pendant edges in the PC-vertex of Cr, 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

Cr is also the PC-vertices of U, where Cr 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

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

edges for every vertices of Cr in U, then, a contradic-

tion. Hence there exist pendant edges for part of vertices of Cr in U. If there exist (r+1)/2 + 1 vertices in Cr 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 Cr. In the neighbor vertices of all pendant vertices of U, if there

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

Thus all pendant vertices of U are joint to the PC-vertices of Cr, 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 Cr, and let v be a k-degree vertex of K1,k+1. Joining u and v by a path Pl, 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 Cr, 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,

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(Cr), by Theorem 2.1 we have, by Lemma 2.2,

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 Cr, 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(Cr), 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(Cr), 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(Cr), 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 U0,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 Cr, by Lemma 2.6 and 2.5 we have. If, using Lemma 2.6, af-

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

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

(r+1)/2 steps, we get kK1, 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 U0,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  The nullity set of Un 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. 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. 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. 3. Cvetkovic, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Academic Press, New York.

4. 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. 5. Cvetkovic, D.M., Gutman, I. and Trinajstic, N. (1972) Graph Theory and Molecular Orbitals, II. Croatica Chemica Acta, 44, 365-374.

6. 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. 7. Sciriha, I. (1998) On Singular Line Graphs of Trees. Congressus Numeratium, 135, 73-91.

8. 8. Sciriha, I. and Gutman, I. (2001) On the Nullity of Line Graphs of Trees. Discrete Mathematics, 232, 35-45.

9. 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. 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. 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. 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. 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. 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. 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. 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. 17. Cheng, B. and Liu, B. (2007) On the Nullity of Graphs. Electronic Journal of Linear Algebra, 16, 60-67.

18. 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.