Prime vertex-minors of a prime graph
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Circle graph obstructions under pivotingJournal of Graph Theory, 2009
- The 3-Connected Graphs with Exactly Three Non-Essential EdgesGraphs and Combinatorics, 2004
- On the Structure of 3-connected Matroids and GraphsEuropean Journal of Combinatorics, 2000
- Matroids and Graphs with Few Non-Essential ElementsGraphs and Combinatorics, 2000
- Circle Graph ObstructionsJournal of Combinatorial Theory, Series B, 1994
- An efficient algorithm to recognize locally equivalent graphsCombinatorica, 1991
- Graphic presentations of isotropic systemsJournal of Combinatorial Theory, Series B, 1988
- Reducing prime graphs and recognizing circle graphsCombinatorica, 1987