Prime vertex-minors of a prime graph

- Title
- Prime vertex-minors of a prime graph

- Author(s)
- Donggyu Kim; Sang-il Oum

- Publication Date
- 2024-05

- Journal
- European Journal of Combinatorics, v.118

- Publisher
- Academic Press

- Abstract
- A graph is prime if it does not admit a partition (A,B) of its vertex set such that min{|A|,|B|}≥2 and the rank of the A×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≠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. © 2023 Elsevier Ltd

- ISSN
- 0195-6698

- Appears in Collections:
- Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)

Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)

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