Premium
Induced matchings in strongly biconvex graphs and some algebraic applications
Author(s) -
Saeedi Madani Sara,
Kiani Dariush
Publication year - 2021
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.201900472
Subject(s) - mathematics , chordal graph , betti number , combinatorics , bipartite graph , monomial , indifference graph , split graph , pathwidth , algebraic number , discrete mathematics , matching (statistics) , cograph , 1 planar graph , graph , line graph , mathematical analysis , statistics
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.