Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInduced matchings in strongly biconvex graphs and some algebraic applications
60
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, motivated by a question posed in cite{AH}, 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 in cite{AH}.
rate research
Read More
Let $G$ be a finite simple graph on the vertex set $V(G) = {x_1, ldots, x_n}$ and $I(G) subset K[V(G)]$ its edge ideal, where $K[V(G)]$ is the polynomial ring in $x_1, ldots, x_n$ over a field $K$ with each ${rm deg} x_i = 1$ and where $I(G)$ is generated by those squarefree quadratic monomials $x_ix_j$ for which ${x_i, x_j}$ is an edge of $G$. In the present paper, given integers $1 leq a leq r$ and $s geq 1$, the existence of a finite connected simple graph $G = G(a, r, d)$ with ${rm im}(G) = a$, ${rm reg}(R/I(G)) = r$ and ${rm deg} h_{K[V(G)]/I(G)} (lambda) = s$, where ${rm im}(G)$ is the induced matching number of $G$ and where $h_{K[V(G)]/I(G)} (lambda)$ is the $h$-polynomial of $K[V(G)]/I(G)$.
Squarefree powers of edge ideals are intimately related to matchings of the underlying graph. In this paper we give bounds for the regularity of squarefree powers of edge ideals, and we consider the question of when such powers are linearly related or have linear resolution. We also consider the so-called squarefree Ratliff property.
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by ErdH{o}s and Bollobas, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/nle p le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2log_q(np)$, where $q= frac{1}{1-p}$.
A biconvex polytope is a convex polytope that is also tropically convex. It is well known that every bounded cell of a tropical linear space is a biconvex polytope, but its converse has been a conjecture. We classify biconvex polytopes, and prove the conjecture by constructing a matroid subdivision dual to a biconvex polytope. In particular, we construct matroids from bipartite graphs, and establish the relationship between bipartite graphs and faces of a biconvex polytope. We also show that there is a bijection between monomials and a maximal set of vertices of a biconvex polytope.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
