Characterization of graphs with given order, given size and given matching number that minimize nullity

详细信息    查看全文

• 作者：Long Wang ^{wanglongxuzhou@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Nullity of graphs ; Dimension of cycle spaces ; Matching number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 May 2016
• 年：2016
• 卷：339
• 期：5
• 页码：1574-1582
• 全文大小：389 K

文摘

Let G=(V(G),E(G))$G=(V\left(G\right),E\left(G\right))$ be a finite undirected graph without loops and multiple edges, c(G)=|E(G)|−|V(G)|+θ(G)$c\left(G\right)=\left|E\left(G\right)\right|-\left|V\left(G\right)\right|+\theta \left(G\right)$ be the dimension of cycle spaces of G$G$ with eddbc2ea599ef6a54bb9ad2" title="Click to view the MathML source">θ(G)$\theta \left(G\right)$ the number of connected components of G$G$, m(G)$m\left(G\right)$ be the matching number of G$G$, and η(G)$\eta \left(G\right)$ be the nullity of G$G$. It was shown in Wang and Wong (2014) that the nullity η(G)$\eta \left(G\right)$ of G$G$ is bounded by an upper bound and a lower bound as 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)|−2m(G)−c(G)$\eta \left(G\right)=\left|V\left(G\right)\right|-2m\left(G\right)-c\left(G\right)$ if and only if the cycles (if any) of G$G$ are pairwise vertex-disjoint and G$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$G$, which is the disjoint union of c(G)$c\left(G\right)$ odd cycles and |V(G)|−2m(G)−c(G)$\left|V\left(G\right)\right|-2m\left(G\right)-c\left(G\right)$ isolated vertices.