论文标题
nullspace顶点分区
Nullspace Vertex Partition in Graphs
论文作者
论文摘要
图的核心顶点集是图形的不变。它由与$ \ {0,1 \} $ - 邻接矩阵的NullSpace向量的非零条目关联的那些顶点组成。图的其余顶点形成了核心 - 孔顶点集。对于具有独立核心顶点的图形，例如两部分的最小配置和树，NullSpace诱导了一个定义明确的三部分顶点分区。该分区的各个部分是核心顶点集，其邻居和远程核心 - 孔子 - 孔子顶点。远程核心的集合 - 被填充的顶点是不毗邻任何核心顶点的顶点。我们证明可以删除此组合，使无效。我们表明，对于具有独立核心顶点的图形，邻接矩阵的子矩阵定义了入射到核心顶点的边缘的矩阵确定邻接矩阵的无效。为了最大程度地提高具有指定无效的最佳网络图的边缘数，我们确定哪些扰动构成了图形邻接矩阵的核心顶点集的足够条件，以保留在添加边缘上。
The core vertex set of a graph is an invariant of the graph. It consists of those vertices associated with the non-zero entries of the nullspace vectors of a $\{0,1\}$-adjacency matrix. The remaining vertices of the graph form the core--forbidden vertex set. For graphs with independent core vertices, such as bipartite minimal configurations and trees, the nullspace induces a well defined three part vertex partition. The parts of this partition are the core vertex set, their neighbours and the remote core--forbidden vertices. The set of the remote core--forbidden vertices are those not adjacent to any core vertex. We show that this set can be removed, leaving the nullity unchanged. We show that for graphs with independent core vertices, the submatrix of the adjacency matrix defining the edges incident to the core vertices determines the nullity of adjacency matrix. To maximize the number of edges for optimal network graphs with a specified nullity, we determine which perturbations make up sufficient conditions for the core vertex set of the adjacency matrix of a graph to be preserved on adding edges.
