Prime vertex-minors of a prime graph

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 253
  • Download : 0
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.
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Issue Date
2024-05
Language
English
Article Type
Article
Citation

EUROPEAN JOURNAL OF COMBINATORICS, v.118

ISSN
0195-6698
DOI
10.1016/j.ejc.2023.103871
URI
http://hdl.handle.net/10203/316856
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0