Characterization of graphs with given order, given size and given matching number that minimize nullity
Characterization of graphs with given order, given size and given matching number that minimize nullity
复制标题
DOI：
10.1016/j.disc.2015.11.023
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Long Wang
中科院分区：
文献类型：
--
作者：
Long Wang
设G=(V(G)，E(G))是一个没有圈和多条边的有限无向图，c(G)=|E(G)|−|V(G)|+θ(G)是G的圈空间的维度，其中θ(G)是G的连通分支数，m(G)是G的匹配数，η(G)是G的零性。在Wang and Wong(2014)中证明了G的零性η(G)有一个上界和一个下界：|V(G)|−2m(G)−c(G)≤η(G)≤|V(G)|−2m(G)+2c(G)。零度达到上界的图已被Song等人刻画(2015)。然而，到目前为止，零度达到下界的图的刻画问题还是个未知数。本文致力于解决这一公开问题，证明了η(G)=|V(G)|−2 m(G)−c(G)当且仅当G的圈(如果有的话)是两点不交的，并且G可以通过删除一个悬挂顶点及其相邻顶点的一系列操作切换到G的一个导出子图，即c(G)奇圈和|V(G)|−2 m(G)−c(G)孤立顶点的不交.
Abstract Let G=(V (G), E (G)) be a finite undirected graph without loops and multiple edges, c (G)=| E (G)|−| V (G)|+ θ (G) be the dimension of cycle spaces of G with θ (G) the number of connected components of G, m (G) be the matching number of G, and η (G) be the nullity of G. It was shown in Wang and Wong (2014) that the nullity η (G) of G is bounded by an upper bound and a lower bound as| V (G)|− 2 m (G)− c (G)≤ η (G)≤| V (G)|− 2 m (G)+ 2 c (G). Graphs with nullity attaining the upper bound have been characterized by Song et al.(2015). However, the problem of characterization of graphs whose nullity attain the lower bound is left open till now. In this paper, we are devoted to solve this open problem, proving that η (G)=| V (G)|− 2 m (G)− c (G) if and only if the cycles (if any) of G are pairwise vertex-disjoint and G can be switched, by a series of operations of deleting a pendant vertex together with its adjacent vertex, to an induced subgraph of G, which is the disjoint union of c (G) odd cycles and| V (G)|− 2 m (G)− c (G) isolated vertices.