文献类型：期刊文献

英文题名：No graph with nullity η(G) = |V(G)|-2m(G)+2c(G)-1

作者：Li, Xin[1];Guo, Ji-Ming[1]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai, Peoples R China

年份：2019

卷号：268

起止页码：130

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;EI(收录号：20192006935032);WOS:【SCI-EXPANDED(收录号:WOS:000488998700012)】；

基金：This research is supported by NSFC, PR china (No. 11371372).

语种：英文

外文关键词：Adjacency matrix; Eigenvalue; Nullity; Graph

摘要：Let G = (V(G), E(G)) be a simple graph with vertex set V(G) and edge set E(G), c(G) = vertical bar E(G)vertical bar - vertical bar V(G)vertical bar + theta(G) be the dimension of cycle spaces of G with theta(G) the number of connected components of G, m(G) be the matching number of G, and eta(G) be the nullity of G. It was shown in Wang and Wong (2014) that the nullity eta(G) of G is bounded by an upper bound and a lower bound as vertical bar V(G)vertical bar - 2m(G) - c(G) <= eta(G) <= vertical bar V(G)vertical bar - 2m(G) 2c(G). Graphs with nullity attaining the upper bound and the lower bound have been characterized by Song et al. (2015) and Wang (2016), respectively. In this paper, we prove that there is no graph with nullity eta(G) = vertical bar V(G)vertical bar - 2m(G) + 2c(G) - 1. For fixed c(G), infinitely many connected graphs with nullity vertical bar V(G)vertical bar - 2m + (G)-2c(G) - k, (0 <= k <= 3c(G), k not equal 1) are also constructed. (C) 2019 Elsevier B.V. All rights reserved.