A graph is prime if it does not admit a partition (A, B) of its vertex set such that min{vertical bar A vertical bar, vertical bar B vertical bar} >= 2 and the rank of the AxB 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 not equal x such that G \ v or G * v \ 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.

- Issue Date
- 2024-05

- Language
- English

- Article Type
- Article

- Citation
EUROPEAN JOURNAL OF COMBINATORICS, v.118

- ISSN
- 0195-6698

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.