The Nullity of Bicyclic Graphs in Terms of Their Matching Number

DOI：10.3770/j.issn:2095-2651.2016.06.001

 作者 单位 萨如拉 内蒙古农业大学理学院, 内蒙古 呼和浩特 010018 长安 福州大学离散数学与理论计算机科学研究中心, 福建 福州 3510001 李建喜 漳州师范学院数学与信息科学系, 福建 漳州 363000

令$G$为$n(G)$个顶点的图且设其匹配数为$m(G)$. 图$G$的零度是指其邻接矩阵中零特征值的重数, 记为$\eta(G)$.众所周知, 若$G$ 是一棵树, 则$\eta(G)=n(G)-2m(G)$. 郭继明等[Jiming GUO, Weigen YAN, Yeongnan YEH, On the nullity and the matching number of unicyclic graphs. Linear Alg. Appl., 431(2009): 1293-1301]证明了当$G$是一个单圈图时, 其零度$\eta(G)$等于$n(G)-2 m(G)-1$, $n(G)-2m(G)$或$n(G)-2m(G)+2$. 本文证明了当$G$是一个双圈图时,其零度$\eta(G)$等于$n(G)-2m(G)$, $n(G)-2m(G)\pm 1$, $n(G)-2m(G)\pm 2$ 或$n(G)-2m(G)+4$; 并且刻画了上述每一种关系.

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.