Prime vertex-minors of a prime graph

Authors:
  • DKDonggyu Kim
    Donggyu Kim
  • SOSang-Il Oum
    Sang-Il Oum

Abstract
A split of a graph is a partition $(A,B)$ of its vertex set such that $\min\{|A|,|B|\} \geq 2$ and for some $A'\subseteq A$ and $B'\subseteq B$, two vertices $x\in A$ and $y\in B$ are adjacent if and only if $x\in A'$ and $y\in B'$. A graph is prime if it has no split. 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. Allys (1994) proved that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle graph. We prove that every prime graph with at least $5$ vertices has at least $2$ non-essential vertices unless it is locally equivalent to a cycle graph. Furthermore, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor.