BROWSE

Related Scientist

's photo.

수리및계산과학연구단
more info

ITEM VIEW & DOWNLOAD

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.publisherAcademic Press-
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.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

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

Browse