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!
Description
Summary: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.
ISSN:0025-584X
1522-2616
DOI:10.1002/mana.201900472