Induced matchings in strongly biconvex graphs and some algebraic applications

In this paper, motivated by a question posed by H. de Alba and D. T. Hoang, we introduce strongly biconvex graphs as a subclass of weakly chordal and bipartite graphs. We give a linear time algorithm to find an induced matching for such graphs and we prove that this algorithm indeed gives a maximum...

Full description

Saved in:
Bibliographic Details
Published in:Mathematische Nachrichten 2021-06, Vol.294 (6), p.1160-1174
Main Authors: Saeedi Madani, Sara, Kiani, Dariush
Format: Article
Language:English
Subjects:
Algorithms
Graph matching
Graphs
Questions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13
cites cdi_FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13
container_end_page 1174
container_issue 6
container_start_page 1160
container_title Mathematische Nachrichten
container_volume 294
creator Saeedi Madani, Sara
Kiani, Dariush
description In this paper, motivated by a question posed by H. de Alba and D. T. Hoang, we introduce strongly biconvex graphs as a subclass of weakly chordal and bipartite graphs. We give a linear time algorithm to find an induced matching for such graphs and we prove that this algorithm indeed gives a maximum induced matching. Applying this algorithm, we provide a strongly biconvex graph whose (monomial) edge ideal does not admit a unique extremal Betti number. Using this constructed graph, we provide an infinite family of the so‐called closed graphs (also known as proper interval graphs) whose binomial edge ideals do not have a unique extremal Betti number. This, in particular, answers the aforementioned question.
doi_str_mv 10.1002/mana.201900472
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2548316717</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2548316717</sourcerecordid><originalsourceid>FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13</originalsourceid><addsrcrecordid>eNo9kM1LwzAchoMoOKdXzwHPnUnaJM1Rhh-DiRcFbyH5Je062qQmnbj_3o2Jp_fy8D7wIHRLyYISwu4HE8yCEaoIqSQ7QzPKGSuYoOIczQ4AL3hdfV6iq5y3hBClpJih11VwO_AOD2aCTRfajLuA85RiaPs9th3E8O1_cJvMuMnYBIdzHDw2fettMh1gM459B2bqYsjX6KIxffY3fztHH0-P78uXYv32vFo-rAsoiZwKYBZM3TDCjXUlLUERWQvpgVtpm0ZYClApqkrJHQMrKLiKOWVJRYE5oOUc3Z1-xxS_dj5Peht3KRyUmvGqLqmQVB6oxYmCFHNOvtFj6gaT9poSfUymj8n0f7LyF4ykYFo</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2548316717</pqid></control><display><type>article</type><title>Induced matchings in strongly biconvex graphs and some algebraic applications</title><source>Wiley</source><creator>Saeedi Madani, Sara ; Kiani, Dariush</creator><creatorcontrib>Saeedi Madani, Sara ; Kiani, Dariush</creatorcontrib><description>In this paper, motivated by a question posed by H. de Alba and D. T. Hoang, we introduce strongly biconvex graphs as a subclass of weakly chordal and bipartite graphs. We give a linear time algorithm to find an induced matching for such graphs and we prove that this algorithm indeed gives a maximum induced matching. Applying this algorithm, we provide a strongly biconvex graph whose (monomial) edge ideal does not admit a unique extremal Betti number. Using this constructed graph, we provide an infinite family of the so‐called closed graphs (also known as proper interval graphs) whose binomial edge ideals do not have a unique extremal Betti number. This, in particular, answers the aforementioned question.</description><identifier>ISSN: 0025-584X</identifier><identifier>EISSN: 1522-2616</identifier><identifier>DOI: 10.1002/mana.201900472</identifier><language>eng</language><publisher>Weinheim: Wiley Subscription Services, Inc</publisher><subject>Algorithms ; Graph matching ; Graphs ; Questions</subject><ispartof>Mathematische Nachrichten, 2021-06, Vol.294 (6), p.1160-1174</ispartof><rights>2021 Wiley‐VCH GmbH</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13</citedby><cites>FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Saeedi Madani, Sara</creatorcontrib><creatorcontrib>Kiani, Dariush</creatorcontrib><title>Induced matchings in strongly biconvex graphs and some algebraic applications</title><title>Mathematische Nachrichten</title><description>In this paper, motivated by a question posed by H. de Alba and D. T. Hoang, we introduce strongly biconvex graphs as a subclass of weakly chordal and bipartite graphs. We give a linear time algorithm to find an induced matching for such graphs and we prove that this algorithm indeed gives a maximum induced matching. Applying this algorithm, we provide a strongly biconvex graph whose (monomial) edge ideal does not admit a unique extremal Betti number. Using this constructed graph, we provide an infinite family of the so‐called closed graphs (also known as proper interval graphs) whose binomial edge ideals do not have a unique extremal Betti number. This, in particular, answers the aforementioned question.</description><subject>Algorithms</subject><subject>Graph matching</subject><subject>Graphs</subject><subject>Questions</subject><issn>0025-584X</issn><issn>1522-2616</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNo9kM1LwzAchoMoOKdXzwHPnUnaJM1Rhh-DiRcFbyH5Je062qQmnbj_3o2Jp_fy8D7wIHRLyYISwu4HE8yCEaoIqSQ7QzPKGSuYoOIczQ4AL3hdfV6iq5y3hBClpJih11VwO_AOD2aCTRfajLuA85RiaPs9th3E8O1_cJvMuMnYBIdzHDw2fettMh1gM459B2bqYsjX6KIxffY3fztHH0-P78uXYv32vFo-rAsoiZwKYBZM3TDCjXUlLUERWQvpgVtpm0ZYClApqkrJHQMrKLiKOWVJRYE5oOUc3Z1-xxS_dj5Peht3KRyUmvGqLqmQVB6oxYmCFHNOvtFj6gaT9poSfUymj8n0f7LyF4ykYFo</recordid><startdate>202106</startdate><enddate>202106</enddate><creator>Saeedi Madani, Sara</creator><creator>Kiani, Dariush</creator><general>Wiley Subscription Services, Inc</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>202106</creationdate><title>Induced matchings in strongly biconvex graphs and some algebraic applications</title><author>Saeedi Madani, Sara ; Kiani, Dariush</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Algorithms</topic><topic>Graph matching</topic><topic>Graphs</topic><topic>Questions</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Saeedi Madani, Sara</creatorcontrib><creatorcontrib>Kiani, Dariush</creatorcontrib><collection>CrossRef</collection><jtitle>Mathematische Nachrichten</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Saeedi Madani, Sara</au><au>Kiani, Dariush</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Induced matchings in strongly biconvex graphs and some algebraic applications</atitle><jtitle>Mathematische Nachrichten</jtitle><date>2021-06</date><risdate>2021</risdate><volume>294</volume><issue>6</issue><spage>1160</spage><epage>1174</epage><pages>1160-1174</pages><issn>0025-584X</issn><eissn>1522-2616</eissn><abstract>In this paper, motivated by a question posed by H. de Alba and D. T. Hoang, we introduce strongly biconvex graphs as a subclass of weakly chordal and bipartite graphs. We give a linear time algorithm to find an induced matching for such graphs and we prove that this algorithm indeed gives a maximum induced matching. Applying this algorithm, we provide a strongly biconvex graph whose (monomial) edge ideal does not admit a unique extremal Betti number. Using this constructed graph, we provide an infinite family of the so‐called closed graphs (also known as proper interval graphs) whose binomial edge ideals do not have a unique extremal Betti number. This, in particular, answers the aforementioned question.</abstract><cop>Weinheim</cop><pub>Wiley Subscription Services, Inc</pub><doi>10.1002/mana.201900472</doi><tpages>15</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0025-584X
ispartof Mathematische Nachrichten, 2021-06, Vol.294 (6), p.1160-1174
issn 0025-584X
1522-2616
language eng
recordid cdi_proquest_journals_2548316717
source Wiley
subjects Algorithms
Graph matching
Graphs
Questions
title Induced matchings in strongly biconvex graphs and some algebraic applications
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T15%3A14%3A14IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Induced%20matchings%20in%20strongly%20biconvex%20graphs%20and%20some%20algebraic%20applications&rft.jtitle=Mathematische%20Nachrichten&rft.au=Saeedi%20Madani,%20Sara&rft.date=2021-06&rft.volume=294&rft.issue=6&rft.spage=1160&rft.epage=1174&rft.pages=1160-1174&rft.issn=0025-584X&rft.eissn=1522-2616&rft_id=info:doi/10.1002/mana.201900472&rft_dat=%3Cproquest_cross%3E2548316717%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c307t-c2bca8f205abd313c907867ec5b7bff6b1cc4919375d2cb61cd42d9b041c2dc13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2548316717&rft_id=info:pmid/&rfr_iscdi=true