The Nullity of Bicyclic Graphs in Terms of Their Matching Number
Received:October 10, 2015  Revised:October 12, 2016
Key Words: nullity   bicyclic graphs   matching number  
Fund Project:Supported by the National Natural Science Foundation of China (Grant Nos.11331003; 11471077).
Author NameAffiliation
Rula SA College of Science, Inner Mongolia Agricultural University, Inner Mongolia 010018, P. R. China 
An CHANG Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fujian 351000, P. R. China 
Jianxi LI Department of Mathematics and Information Science, Zhangzhou Normal University, Fujian 363000, P. R. China 
Hits: 2053
Download times: 1965
      Let $G$ be a graph with $n(G)$ vertices and $m( G )$ be its matching number. The nullity of $G$, denoted by $\eta( G )$, is the multiplicity of the eigenvalue zero of adjacency matrix of $G$. It is well known that if $G$ is a tree, then $\eta( G )=n( G )-2 m( G )$. Guo et al. [Jiming GUO, Weigen YAN, Yeongnan YEH. On the nullity and the matching number of unicyclic graphs. Linear Alg. Appl., 2009, 431: 1293--1301] proved that if $G$ is a unicyclic graph, then $\eta( G )$ equals $n( G ) - 2 m( G ) -1$, $n( G ) - 2 m( G ) $, or $n( G ) - 2 m( G ) +2$. In this paper, we prove that if $G$ is a bicyclic graph, then $\eta( G )$ equals $n( G ) - 2 m( G ) $, $n (G)-2m(G)\pm 1 $, $n( G ) - 2 m( G )\pm 2$ or $n( G ) - 2 m (G ) +4$. We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.
View Full Text  View/Add Comment  Download reader