Induced matchings in strongly biconvex graphs and some algebraic applications

Sara Saeedi Madani and Dariush Kiani

Mathematische Nachrichten, 2021, vol. 294, issue 6, 1160-1174

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.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/mana.201900472

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:mathna:v:294:y:2021:i:6:p:1160-1174

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0025-584X

Access Statistics for this article

Mathematische Nachrichten is currently edited by Robert Denk

More articles in Mathematische Nachrichten from Wiley Blackwell
Bibliographic data for series maintained by Wiley Content Delivery ().