### BROWSE

#### Related Scientist

수리및계산과학연구단

Prime vertex-minors of a prime graph

DC Field Value Language
dc.contributor.authorDonggyu Kim-
dc.contributor.authorSang-il Oum-
dc.date.accessioned2024-01-16T22:00:16Z-
dc.date.available2024-01-16T22:00:16Z-
dc.date.created2023-11-28-
dc.date.issued2024-05-
dc.identifier.issn0195-6698-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/14626-
dc.description.abstractA 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-
dc.language영어-
dc.titlePrime vertex-minors of a prime graph-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid001120714700001-
dc.identifier.scopusid2-s2.0-85177242163-
dc.identifier.rimsid82118-
dc.contributor.affiliatedAuthorDonggyu Kim-
dc.contributor.affiliatedAuthorSang-il Oum-
dc.identifier.doi10.1016/j.ejc.2023.103871-
dc.identifier.bibliographicCitationEuropean Journal of Combinatorics, v.118-
dc.relation.isPartOfEuropean Journal of Combinatorics-
dc.citation.titleEuropean Journal of Combinatorics-
dc.citation.volume118-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordPlusRANK-WIDTH-
dc.subject.keywordPlusCONNECTIVITY-
dc.subject.keywordPlusMATROIDS-
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.