BROWSE

Related Scientist

Chakraborti, Debsoumya's photo.

Chakraborti, Debsoumya
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Minimizing the number of edges in K(s,t)-saturated bipartite graphs

DC Field Value Language
dc.contributor.authorDEBSOUMYA CHAKRABORTI-
dc.contributor.authorChen, Da Qi-
dc.contributor.authorHasabnis, Mihir-
dc.date.accessioned2021-08-05T05:30:22Z-
dc.date.accessioned2021-08-05T05:30:22Z-
dc.date.available2021-08-05T05:30:22Z-
dc.date.available2021-08-05T05:30:22Z-
dc.date.created2021-07-07-
dc.date.issued2021-01-
dc.identifier.issn0895-4801-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/10041-
dc.description.abstract© 2021 Society for Industrial and Applied Mathematics.This paper considers an edge minimization problem in saturated bipartite graphs. An n by n bipartite graph G is H-saturated if G does not contain a subgraph isomorphic to H but adding any missing edge to G creates a copy of H. More than half a century ago, Wessel and Bollobas independently solved the problem of minimizing the number of edges in K(s,t)-saturated graphs, where K(s,t) is the "ordered" complete bipartite graph with s vertices from the first color class and t from the second. However, the very natural "unordered" analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When s = t, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korandi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in K(s,t)-saturated n by n bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for s = t - 1 with the classification of the extremal graphs. We also improve the estimates of Gan, Korandi, and Sudakov for general s and t, and for all sufficiently large n.-
dc.language영어-
dc.publisherSociety for Industrial and Applied Mathematics Publications-
dc.titleMinimizing the number of edges in K(s,t)-saturated bipartite graphs-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid000674142200027-
dc.identifier.scopusid2-s2.0-85108682475-
dc.identifier.rimsid75897-
dc.contributor.affiliatedAuthorDEBSOUMYA CHAKRABORTI-
dc.identifier.doi10.1137/20M1368835-
dc.identifier.bibliographicCitationSIAM JOURNAL ON DISCRETE MATHEMATICS, v.35, no.2, pp.1165 - 1181-
dc.relation.isPartOfSIAM JOURNAL ON DISCRETE MATHEMATICS-
dc.citation.titleSIAM JOURNAL ON DISCRETE MATHEMATICS-
dc.citation.volume35-
dc.citation.number2-
dc.citation.startPage1165-
dc.citation.endPage1181-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics, Applied-
dc.subject.keywordAuthorgraph saturation-
dc.subject.keywordAuthorcomplete bipartite graph-
dc.subject.keywordAuthoredge minimization-
Appears in Collections:
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