论文标题
素数的主要顶点少量
Prime vertex-minors of a prime graph
论文作者
论文摘要
图形如果不接收其顶点集的分区$（a，b）$，以至于$ \ min \ {| a |，| b | \} \ geq 2 $以及$ a \ times b $ subbatrix的等级最多是$ 1 $ $ 1 $。如果三种$ v $的顶点最少的降低中至少有两种，则图表的顶点$ v $是非必需的。 在1994年，Allys证明，除非局部等于循环图，否则每个具有至少四个顶点的素数具有非必需的顶点。我们证明，除非局部等于循环图，否则每个具有至少四个顶点的素图至少具有两个非必需的顶点。作为推论，我们表明，对于一个至少六个顶点和顶点$ x $的素图$ g $，有一个顶点$ v \ ne x $，使得$ g \ setminus v $或$ g * v \ setminus v $是prime，除非$ x $与所有其他顶点和$ g $ ISMOMORPHIC相邻，否则$ x $是奇数属于奇数的， 此外，我们表明，具有至少四个顶点的素数至少具有三个非必需的顶点，除非它在局部等同于一个图形，该图与两个没有共同邻居的两个固定不同顶点之间的至少两个内部分散路径组成。我们还证明了枢轴少量的结果。
A graph is prime if it does not admit a partition $(A,B)$ of its vertex set such that $\min\{|A|,|B|\} \geq 2$ and the rank of the $A\times B$ submatrix of its adjacency matrix is at most $1$. A vertex $v$ of a graph is non-essential if at least two of the three kinds of vertex-minor reductions at $v$ result in prime graphs. In 1994, Allys proved that every prime graph with at least four vertices has a non-essential vertex unless it is locally equivalent to a cycle graph. We prove that every prime graph with at least four vertices has at least two non-essential vertices unless it is locally equivalent to a cycle graph. As a corollary, we show that for a prime graph $G$ with at least six vertices and a vertex $x$, there is a vertex $v \ne x$ such that $G \setminus v$ or $G * v \setminus v$ is prime, unless $x$ is adjacent to all other vertices and $G$ is isomorphic to a particular graph on odd number of vertices. Furthermore, we show that a prime graph with at least four vertices has at least three non-essential vertices, unless it is locally equivalent to a graph consisting of at least two internally-disjoint paths between two fixed distinct vertices having no common neighbors. We also prove analogous results for pivot-minors.
