Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices

作者：Ma, Xiaobin; Wong, Dein^*; Tian, Fenglei

来源：Discrete Applied Mathematics, 2016, 215: 171-176.

DOI：10.1016/j.dam.2016.07.010

• Nullity of graphs
• Dimension of cycle space
• Pendant vertices

Let G be a undirected graph without loops and multiple edges. By eta(G), theta(G) and p(G) we respectively denote the nullity, the dimension of cycle space, and the number of pendant vertices of G. If each component of G contains at least two vertices, then it is proved that eta(G) <= 2 theta(G) + p(G), the equality is attained if and only if every component of G is a cycle with size a multiple of 4.

• 出版日期2016-12-31
• 单位中国矿业大学（北京）