Menu
Elimination ideals are monomial ideals associated to simple graphs, not necessarily square–free, was introduced by Anwar and Khalid. These ideals are Borel type. In this paper, we obtain sharp combinatorial upper bounds of the Castelnuovo–Mumford regularity of elimination ideals corresponding to certain family of graphs.
Let \(S=k[x_1,\ldots,x_n]\) be a polynomial ring in \(n\)–variables over an infinite field \(k\). We say that a monomial ideal \(I \subset S\) is of Borel type, see [1], if it satisfies the following condition: \((I : x_j^{\infty} ) = (I : (x_1, \ldots, x_j )^{\infty})\) for all \(1 \leq j \leq n.\) The Castelnuovo–Mumford regularity of \(I\) is the number \(reg(I) = \max\{ j-i | \beta_{ij} (I) \neq 0\},\) where \(\beta_{ij}(I)\) are the graded Betti numbers of \(I\). The regularity of monomial ideals of Borel type is extensively studied, see for instance [2,3,4,5].
Let \(G\) be a simple connected
graph on the vertex–set \(V(G)=\{x_1,\ldots,x_n\}\) and edge–set
\(E(G)\). There are a number of ways to
study the algebraic properties of the graph by associating a monomial
ideal to it, well known among all are edge–ideals. Recently, Anwar and
Khalid in [3] introduced a
new class of monomial ideals, namely; elimination
ideals \(I_{D}(G)\),
associated to \(G\). They showed that
the elimination ideals are monomial ideals of Borel type. They gave the
description of Graphical Degree Stability of graph
\(G\) denoted by \(\text{Stab}_{d}(G)\); a combinatorial
measure associated to \(G\). They gave
a systematic procedure to compute the graphical degree stability, namely
Dominating Vertex Elimination Method (DVE method).
They computed the upper bound of the Castelnuovo–Mumford regularity of
elimination ideals for complete graph, star graph, line graph, cyclic
graph, fan graph, friendship graph and wheel graph.
Motivated from [3], we
further extended this study to other family of graphs. We succeeded to
obtain a sharp combinatorial bound for the Castelnuovo–Mumford
regularity of elimination ideals associated to regular Harary graphs
\(H_{n-2, n}\) (see theorem 3). We
obtain similar result for the join of complete graph and Path Graph;
\(K_n\vee P_m\) (see theorem 3) and for
complete bipartite graph; \(K_{m,n}\)
(see theorem 4)
Throughout in this paper, we consider \(G\) as a finite simple connected graph with
vertex set \(V(G)=\{x_{1},\ldots,x_{n}\}\) and \(S=k[x_1,\ldots,x_n]\) be the associated
polynomial ring over an infinite field \(k\), also the edge set of \(G\) will be denoted by \(E(G)\). As \(|V(G)|\) is finite, we may use the set
\([n]=\{1,2,\ldots,n\}\) instead of
\(V(G)\) and we shall always use \([n]\) to label the vertices in
figures.
Let \(x_{i}\in V(G),\) then the number
of edges incident to \(x_{i}\) is
called the degree of \(x_{i}\) and is
denoted by \(\deg(x_{i})\), if \(\deg(x_{i})\geq \deg(x_{j})\) for all \(x_{j}\in V(G),\) then \(x_{i}\) is called dominating
vertex of \(G,\) and the set of
all dominating vertices of \(G\) is
called the dominating set of \(G,\) denoted as \(D(G).\) A vertex \(x_{i}\in V(G)\) with \(\deg(x_{i})=0\) is called an isolated
vertex of \(G.\) We call \(G\) a scattered graph, if it has
at least one isolated vertex, otherwise, non-scattered graph. A
finite sequence of nonnegative integers is called graphical degree
sequence if it is a degree sequence of some graph. Throughout in
this paper, we assume that \(\deg(x_{1})\geq
\deg(x_{2})\geq \dots \geq
\deg(x_{n})\) in \(G\). Now, we
recall important definitions from [3].
Definition 1. Let \(G_{i}\) be a graph and pick a vertex \(x\) in \(D(G_{i})\) such that \(G_{i+1}:=G_{i}-\{x\}\) is an induced, non-scattered subgraph of \(G_{i}\). This method of obtaining an induced, non-scattered subgraph \(G_{i+1}\) from \(G_{i}\) by eliminating a vertex from the dominating set \(D(G_{i})\) is called the dominating vertex elimination method, the method is known as DVE method. See [3] for more details.
Let \(G:=G_{0}\) be a graph with vertex set \([n]\), then the length of the maximum chain of induced, non scattered subgraphs of \(G\) obtained by successively using DVE method is called the graphical degree stability of \(G,\) and it is formally denoted by \(\text{Stab}_{d}(G).\) In other words, if \(G:=G_{0}\supset G_{1}\supset\cdots \supset G_{k}\) is the maximum chain of induced, non scattered subgraphs of \(G\) then \(\text{Stab}_{d}(G)=k.\) Note that \(G_{k}\) is a subgraph of \(G\) with vertex set \([n-k].\)
Definition 2. Let \(G_{i}\) be a graph with vertex set \(V(G_{i})=\{x_{1},x_{2},\dots,x_{i}\}\) and having the degree sequence \((d_{1},d_{2},\dots,d_{i})\), then the ideal \(Q_{i}:=\langle x_{1}^{d_{1}},x_{2}^{d_{2}},\dots,x_{i}^{d_{i}}\rangle\) is called the sequential ideal of \(G_{i}\). Let \(G:=G_{0}\supset G_{1}\supset\dots \supset G_{k}\) be the maximum chain of induced, non scattered subgraphs of \(G\) obtained by DVE method with \(\text{Stab}_{d}(G)=k,\) then \(I_{D}(G):=\bigcap\limits_{j=0}^{k}Q_{j}\) is called the elimination ideal of \(G.\)
Now, we recall some definitions from graph theory.
Definition 3. Let \(G\) and \(H\) be two graphs with mutually disjoint vertex sets \(V(G)=\{u_{1},u_{2}\dots,u_{n}\}\) and \(V(H)=\{w_{1},w_{2},\dots,w_{m}\}.\) A graph, denoted by \(G\vee H\), is called the join of \(G\) and \(H\) if \(V(G\vee H)=V(G)\cup V(H)\) and \(E(G\vee H)=E(G)\cup E(H)\cup \{u_{i}w_{j}|u_{i}\in V(G), \ w_{j}\in V(H)\}\).
Definition 4. Let \(G\) be a graph with vertex set \(V(G).\) A subset \(X\) of \(V(G)\) is called an independent set if no two vertices of \(X\) are adjacent. A k-partite graph is a graph whose vertex set \(V(G)\) can be partitioned into k distinct independent sets. A complete k-partite graph is a k-partite graph with every two vertices from distinct independent sets are adjacent. If k=2, then graph is bipartite.
We conclude this section by recalling some important definitions and
results regarding stable properties of ideals.
Let \(I\subset S=k[x_{1},\dots,x_{n}]\)
be a monomial ideal. For any monomial \(u\in
S\) set \(m(u):=\max\{j| \
x_{j}|u\}\) and \(m(I)=\max\{m(u)| \
u\in G(I)\}\), where \(G(I)\)
denotes the set of minimal monomial generators of \(I.\) The highest degree of monomial in
\(G(I)\) is denoted by \(\deg(I)\). Also, \(I_{\geq t}\) is the monomial ideal
generated by monomials of \(I\) of
degree \(\geq\) t. A monomial ideal
\(I\) is stable if for each
monomial \(u\in I\) we have \(x_{j}.\frac{u}{x_{m(u)}}\in I\) for all
\(1\leq j<m(u)\). We set \(q(I)=m(I)(\deg(I)-1)+1\).
Eisenbud, Reeves and Totaro proved the following result in [6].
Theorem 1. Let \(I\) be a monomial ideal with \(\deg(I)=d\) and \(e\geq d\) be an integer such that \(I_{\geq e}\) is stable, then \(reg(I)\leq e\).
In [2], the authors gave the following bound for the regularity of Borel type ideals.
Proposition 1. Let \(I\) be a Borel type ideal, then \(reg(I)\leq q(I)\).
Remark 1. As \(Ass\big(S/I_{D}(G)\big)\) is totally ordered under inclusion, therefore \(I_{D}(G)\) is a Borel type ideal by [2].
In [2], the authors proved the following:
Proposition 2. If \(I\) and \(J\) are two monomial ideals with \(s\geq \deg(I)\) and \(t\geq \deg(J)\) be two integers such that \(I_{\geq s}\) and \(J_{\geq t}\) are stable ideals, then \((I\cap J)_{\geq\max\{s,t\}}\) is stable ideal.
In this section, we give our main results regarding the Castelnuovo–Mumford regularity of elimination ideals for different classes of graphs.
First, we recall the definition of Harary graph.
Definition 5.
Harary graph \(H_{k,n}\) is
the smallest \(k\)-connected graph with
\(n\) vertices. Let us have a set \(V=\{x_{1},x_{2},\ldots,x_{n}\}\) of \(n\) vertices, then the construction of
Harary graphs are as follows:
Case I: If \(k=2m<n\) \((n
\ may \ be \ even \ or \ odd),\) then place all \(n\) vertices in a circle and join each
vertex \(x_{i}\) to its \(m\) consecutive left vertices and to its
\(m\) consecutive right vertices by
drawing edges.
Case II: Let \(n\) is
even. If \(k=2m+1<n,\) then first
construct \(H_{2m,n}\) and then join
each vertex \(x_{i}, \ 1\leq i\leq
\frac{n}{2},\) to its diametrically opposite vertex.
Case III: If both \(k\) and \(n\) are odd then first construct \(H_{k-1,n}\), then join each vertex \(x_{i}, \ 1\leq i\leq
\frac{n-1}{2}+1,\) with vertex \(x_{i+\frac{n-1}{2}}.\)
Note that the graphs in Case I and Case II are regular. Also note that if \(k=n-1\) then Case I and Case II suggest that \(H_{k,n}\) is a complete graph \(K_{n}\). When \(n\) is even, the diametrically opposite vertex of \(x_{i}\) is given by: \[\begin{cases} x_{i}\leftrightarrow x_{i+\frac{n}{2}} & if \ 1\leq i\leq \frac{n}{2}\\ x_{i}\leftrightarrow x_{i-\frac{n}{2}} & if \ \frac{n}{2}+1\leq i\leq n \end{cases}\]
We are interested in computing the regularity of elimination ideal associated to \(H_{n-2,n}\) when \(n\) is even and degree \(k=n-2.\) We begin by computing the graphical degree stability of \(H_{n-2,n}\).
Lemma 1. Let \(H_{n-2,n}\) be a regular Harary graph with even vertices \(n=2r\geq4\) and degree of each vertex is \(n-2\), then \(\text{Stab}_{d}(H_{n-2,n}) = n-3\).
Proof. We prove it by induction on \(r\) for \(n=2r\geq 4.\) For \(r=2\), \(G_{0}:=H_{2,4}\) is a regular graph with degree sequence \((2,2,2,2)\), so its dominating set will be \(D(G_{0})=\{x_{1},x_{2},x_{3},x_{4}\}\). Now, pick vertex \(x_{1}\in D(G_{0})\), after removing \(x_{1}\) we get \(G_{1}\) with degree sequence \((2,1,1)\). The process will stop at \(G_{1}\) and \(\text{Stab}_{d}(H_{2,4})=1.\)
Consider the result is true for \(r=p\), i.e. \(\text{Stab}_{d}(H_{2p-2,2p}) = 2p-3.\)
Now take \(r=p+1\), and let \(G_{0}:=H_{2p,2p+2}\). The degree sequence of \(G_{0}\) is \(\underbrace{(2p,\dots,2p)}_\text{(2p+2)-tuple}\) with dominating set is \(D(G_{0})=\{x_{1}, x_{2}, \dots,x_{2p+2}\}\). Choose vertex \(x_{1}\) from \(D(G_{0})\) and apply DVE method, we get \(G_{1}\) with \(D(G_{1})\) solely consists of diametrically opposite vertex (see Definition 1) of \(x_{1}\) of degree \(2p\). All other vertices are of degree \(p-1\). The degree sequence of \(G_{1}\) will be \(\underbrace{(2p,2p-1,\dots,2p-1)}_\text{(2p+1)-tuple}\). On removing \(x_{1}\) (after relabeling of the vertices) we get \(G_{2}:=H_{2p-2,2p}\). Now \[\text{Stab}_{d}(H_{2p-2,2p}) = 2p-3\] \[\Rightarrow \text{Stab}_{d}(H_{2p,2p+2}) = 2+\text{Stab}_{d}(H_{2p-2,2p})= (2p+2)-3\] which is required.
Example 1. 1] Consider \(H_{4,6}\), here \(n=6\) and \(k=4\), see Figure \(1\).
Corollary 2. Let \(H_{n-2,n}\) be a regular Harary graph with even vertices \(n\geq4\) and degree of each vertex is \(n-2\), then its sequential ideal is given as follows: \[Q_{i}=\begin{cases} \langle x_{1}^{n-i-2},x_{2}^{n-i-2},\dots,x_{n-i}^{n-i-2}\rangle & if \ i \ is \ even \\ \langle x_{1}^{n-i-1},x_{2}^{n-i-2},\dots,x_{n-i}^{n-i-2}\rangle & if \ i \ is \ odd \end{cases}\] where \(0\leq i\leq n-3\).
Proof. The proof follows from the definition of elimination ideal and lemma 1.
Theorem 2. Let \(H_{n-2,n}\) be a regular Harary graph with even vertices \(n\geq4\) and degree of each vertex is \(n-2\), then \(reg(I_{D}(H_{n-2,n}))\leq (n-1)(n-2)-1\).
Proof. We shall discuss the two cases of corollary 2 separately.
Case 1. When \(i\in\{0,2,4,\dots,n-4\}\), the sequential ideal is given as \(Q_{i}=\langle x_{1}^{a_{1}},\dots,x_{n-i}^{a_{n-i}}\rangle\) where \(a_{j}=n-i-2\) for all \(1\leq j\leq n-i\). Let \(\gamma(i)=a_{i}(a_{i}+1)-1\) for all \(i\in\{0,2,4,\dots,n-4\}\). We shall show that \(Q_{i_{\geq \gamma(i)}}\) is a stable ideal. Take \(u\in Q_{i_{\geq \gamma(i)}}\), then \(u=vx_{k}^{a_{k}}\) for some \(1\leq k\leq n-i\) where \(v\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma(i)-a_{k}}\).
If \(m(u)>k,\) then \(\frac{x_{l}u}{x_{m(u)}}=\frac{x_{l}v}{x_{m(u)}}x_{k}^{a_{k}}\in Q_{i_{\geq \gamma(i)}}\) for all \(l<m(u)\). So, \(Q_{i_{\geq \gamma(i)}}\) is stable.
If \(m(u)=k,\) then clearly \(u\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma(i)}\) which is a stable ideal and \(Q_{i_{\geq \gamma(i)}}\subseteq\langle x_{1},\dots,x_{n-i}\rangle^{\gamma(i)}\). It remains to show that \(\langle x_{1},\dots,x_{n-i}\rangle^{\gamma(i)}\subseteq Q_{i_{\geq \gamma(i)}}\). Let \(w\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma(i)}\) then \(w=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n-i}^{\beta_{n-i}}\) with \(\beta_{s}\geq0\) for all \(1\leq s\leq n-i\) and \(\Sigma_{s=1}^{n-i}\beta_{s}\geq \gamma(i)\). Therefore, there exist at least one \(r\in\{1,\dots,n-i\}\) such that \(\beta_{r}\geq a_{r}\) and \(w=(x_{1}^{\beta_{1}}\cdots x_{r}^{\beta_{r}-a_{r}}\cdots x_{n-i}^{\beta_{n-i}})x_{r}^{a_{r}}\in Q_{i_{\geq \gamma(i)}}\), hence the result follows.
Case 2. When \(i\in\{1,3,5,\dots,n-3\}\), the sequential ideal then is given as \(Q_{i}=\langle x_{1}^{a_{1}},\dots,x_{n-i}^{a_{n-i}}\rangle\) where \[a_{j}=\begin{cases} n-i-1 & if \ j=1 \\ n-i-2 & if \ 2\leq j\leq n-i \end{cases}\] Let \(\gamma'(i)=a_{i}(a_{i}+1)\) for all \(i\in\{1,3,5,\dots,n-3\}\), then we shall show that \(Q_{i_{\geq \gamma'(i)}}\) is a stable ideal. Take \(u\in Q_{i_{\geq \gamma'(i)}}\), then \(u=vx_{k}^{a_{k}}\) for some \(1\leq k\leq n-i\) where \(v\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma'(i)-a_{k}}\).
If \(m(u)>k,\) then \(\frac{x_{l}u}{x_{m(u)}}=\frac{x_{l}v}{x_{m(u)}}x_{k}^{a_{k}}\in Q_{i_{\geq \gamma'(i)}}\) for all \(l<m(u)\). So, \(Q_{i_{\geq \gamma'(i)}}\) is stable.
If \(m(u)=k,\) then clearly \(u\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma'(i)}\) which is stable ideal and \(Q_{i_{\geq \gamma'(i)}}\subseteq\langle x_{1},\dots,x_{n-i}\rangle^{\gamma'(i)}\). We are to show that \(\langle x_{1},\dots,x_{n-i}\rangle^{\gamma'(i)}\subseteq Q_{i_{\geq \gamma'(i)}}\). Let \(w\in\langle x_{1},\dots,x_{n-i}\rangle^{\gamma'(i)}\) then \(w=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{n-i}^{\beta_{n-i}}\) with \(\beta_{s}\geq0\) for all \(1\leq s\leq n-i\) and \(\Sigma_{s=1}^{n-i}\beta_{s}\geq \gamma'(i)\). Therefore, there exist at least one \(r\in\{1,\dots,n-i\}\) such that \(\beta_{r}\geq a_{r}\) and \(w=(x_{1}^{\beta_{1}}\cdots x_{r}^{\beta_{r}-a_{r}}\cdots x_{n-i}^{\beta_{n-i}})x_{r}^{a_{r}}\in Q_{i_{\geq \gamma'(i)}}\) and the result follows.
By lemma 1, \(\text{Stab}_{d}(H_{n-2,n}) = n-3\), so the corresponding elimination ideal is given as \(I_{D}(H_{n-2,n})=\bigcap\limits^{n-3}_{i=0}Q_{i}\). By proposition 1, \(I_{D}(H_{n-2,n})\) is stable for \(\gamma_{0}\), where \[\gamma_{0}=\max\{\gamma(i), \gamma'(j)|i\in\{0,2,\dots,n-4\},j\in\{1,3,\dots,n-3\}\}=(n-1)(n-2)-1\] and by theorem 1 \(reg(I_{D}(H_{n-2,n}))\leq (n-1)(n-2)-1.\)
Remark 2. In Example 1,
\(D(G_{0})=\{x_{1},x_{2},\dots,x_{6}\}\) with
\(Q_{0}= \langle
x_{1}^{4},x_{2}^{4},\dots,x_{6}^{4}\rangle\) and \(reg(Q_{0})=19\).
\(D(G_{1})=\{x_{1}\}\) with \(Q_{1}= \langle x_{1}^{4},x_{2}^{3},\dots,x_{5}^{3}\rangle\) and \(reg(Q_{1})=12\)
\(D(G_{2})=\{x_{1},x_{2},x_{3},x_{4}\}\) with \(Q_{2}= \langle x_{1}^{2},x_{2}^{2},x_{3}^{2},x_{4}^{2}\rangle\) and \(reg(Q_{2})=5\)
\(D(G_{3})=\{x_{1}\}\) with \(Q_{3}= \langle x_{1}^{2},x_{2},x_{3}\rangle\) and \(reg(Q_{3})=2\)
In [3], following formula is given to compute the graphical degree stability of path graph:
Proposition 3. Let \(P_{m}, \ m\geq3\), be a path graph then: \[\text{Stab}_{d}(P_{m})=\begin{cases} \frac{m-3}{3} & if \ m\equiv 0 \ (mod \ 3) \\ \frac{m-4}{3} & if \ m\equiv 1 \ (mod \ 3) \\ \frac{m-2}{3} & if \ m\equiv 2 \ (mod \ 3) \end{cases}\]
Lemma 1. Let \(K_{n}, n\geq2\) be a complete graph and \(P_{m}, \ m\geq4\) be a path graph then: \[\text{Stab}_{d}(K_{n}\vee P_{m}) = n+\text{Stab}_{d}(P_{m})\]
Proof. We shall prove it by induction on \(n\). Let \(n=2\) and \(m=4\), then \(G_{0}:=K_{2}\vee P_{4}\) with degree sequence \((5,5,4,4,3,3)\) and \(D(G_{0})=\{x_{1},x_{2}\}.\) Without loss of generality, remove \(x_{1}\in D(G_{0})\) to get \(G_{1}\) with the degree sequence \((4,3,3,2,2)\). So, \(D(G_{1})=\{x_{1}\}\) and on removing \(x_{1}\in D(G_{1})\), we get \(G_{2}=P_{4}.\) \[\implies \ \ \ \text{Stab}_{d}(K_{2}\vee P_{4})= 2+\text{Stab}_{d}(P_{4})\] Suppose that result is true for \(n=q\) and \(m=r\), then \(\text{Stab}_{d}(K_{q}\vee P_{r}) = q+\text{Stab}_{d}(P_{r})\).
Consider \(n=q+1\) and \(m=r\) then \(G_{0}:=K_{q+1}\vee P_{r}\) with degree sequence \((\underbrace{q+r,\dots,q+r}_\text{(q+1)-tuple},\underbrace{q+3,\dots,q+3}_\text{(r-2)-tuple},q+2,q+2)\) and \(|V(G_{0}|=q+r+1\). Since \(r\geq4\), \(D(G_{0})=\{x_{1},\dots,x_{q+1}\}\) which are precisely the vertices that were initially belonged to \(K_{q+1}.\) As removing any vertex from \(K_{q+1}\) gives \(K_{q},\) So without loss of generality pick \(x_{1}\in D(G_{0})\) and on removing it, we get \(G_{1}=K_{q}\vee P_{r}.\) \[\implies \ \ \ \text{Stab}_{d}(K_{q+1}\vee P_{r})= 1+\text{Stab}_{d}(K_{q}\vee P_{r})=1+q+\text{Stab}_{d}(P_{r})\] which completes the proof.
Corollary 3. Let \(K_{n},n\geq 2\) be a complete graph and \(P_{m},m\geq 4\) be a path graph, then the sequential ideal of \(K_{n}\vee P_{m}\) is given as follows: \[Q_{i}=\begin{cases} \langle x_{1}^{m+n-i-1},\dots, x_{n-i}^{m+n-i-1},x_{n-i+1}^{n-i+2},\dots,x_{m+n-i-2}^{n-i+2},x_{m+n-i-1}^{n-i+1},x_{m+n-i}^{n-i+1}\rangle & if \ 0\leq i\leq n-1 \\ \langle x_{1}^{2},x_{2}^{2},\dots,x_{m-3(i-n)-2}^{2},x_{m-3(i-n)-1},\dots,x_{m+n-i}\rangle & if \ n\leq i\leq n+p \end{cases}\] where \(p=\text{Stab}_{d}(P_{m})\)
Theorem 3. Let \(K_{n},n\geq 2\) be a complete graph and \(P_{m},m\geq 4\) be a path graph then \(reg(I_{D}(K_{n}\vee P_{m}))\leq n^{2}+2n(m-1)+m-1.\)
Proof. We shall discuss the two cases of corollary 3 separately.
Case 1. When \(0\leq i\leq n-1\), the sequential ideal is given as \(Q_{i}=\langle x_{1}^{a_{1}},\dots,x_{m+n-i}^{a_{m+n-i}}\rangle\) where \[a_{j}=\begin{cases} m+n-i+1 & if \ 1\leq j\leq n-i \\ n-i+2 & if \ n-i+1\leq j\leq m+n-i-2\\ n-i+1 & if \ n-i+1\leq j\leq m+n-i. \end{cases}\]
Let \(\gamma(i)=(n-i)^{2}+2(m-1)(n-i)+m-1\) for all \(0\leq i\leq n-1\). We shall show that \(Q_{i_{\geq \gamma(i)}}\) is a stable ideal. Take \(u\in Q_{i_{\geq \gamma(i)}}\), then \(u=vx_{k}^{a_{k}}\) for some \(1\leq k\leq m+n-i\) where \(v\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)-a_{k}}\).
If \(m(u)>k,\) then \(\frac{x_{l}u}{x_{m(u)}}=\frac{x_{l}v}{x_{m(u)}}x_{k}^{a_{k}}\in Q_{i_{\geq \gamma(i)}}\) for all \(l<m(u)\). So, \(Q_{i_{\geq \gamma(i)}}\) is stable.
If \(m(u)=k,\) then clearly \(u\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\) and \(Q_{i_{\geq \gamma(i)}}\subseteq\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\). We are to show that \(\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\subseteq Q_{i_{\geq \gamma(i)}}\). Let \(w\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\) then \(w=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{m+n-i}^{\beta_{m+n-i}}\) with \(\beta_{s}\geq0\) for all \(1\leq s\leq m+n-i\) and \(\Sigma_{s=1}^{m+n-i}\beta_{s}\geq \gamma(i)\). Therefore, there exist at least one \(r\in\{1,\dots,m+n-i\}\) such that \(\beta_{r}\geq a_{r}\) and \(w=(x_{1}^{\beta_{1}}\cdots x_{r}^{\beta_{r}-a_{r}}\cdots x_{m+n-i}^{\beta_{m+n-i}})x_{r}^{a_{r}}\in Q_{i_{\geq \gamma(i)}}\) and the result follows.
Case 2. When \(n\leq i\leq n+p\), the sequential ideal is given as \(Q_{i}=\langle x_{1}^{a_{1}},\dots,x_{m+n-i}^{a_{m+n-i}}\rangle\) where \[a_{j}=\begin{cases} 2 & if \ 1\leq j\leq m-3(i-n)-2 \\ 1 & if \ m-3(i-n)-1\leq j\leq m+n-i. \end{cases}\]
Let \(\gamma'(i)=m-3(i-n)-1\) for all \(n\leq i\leq n+p\), then we shall show that \(Q_{i_{\geq \gamma'(i)}}\) is a stable ideal. Take \(u\in Q_{i_{\geq \gamma'(i)}}\), then \(u=vx_{k}^{a_{k}}\) for some \(1\leq k\leq m+n-i\) where \(v\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma'(i)-a_{k}}\).
If \(m(u)>k,\) then \(\frac{x_{l}u}{x_{m(u)}}=\frac{x_{l}v}{x_{m(u)}}x_{k}^{a_{k}}\in Q_{i_{\geq \gamma'(i)}}\) for all \(l<m(u)\). So, \(Q_{i_{\geq \gamma'(i)}}\) is stable.
If \(m(u)=k,\) then clearly \(u\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma'(i)}\) and \(Q_{i_{\geq \gamma'(i)}}\subseteq\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma'(i)}\). We are to show that \(\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma'(i)}\subseteq Q_{i_{\geq \gamma'(i)}}\). Let \(w\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma'(i)}\) then \(w=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{m+n-i}^{\beta_{m+n-i}}\) with \(\beta_{s}\geq0\) for all \(1\leq s\leq m+n-i\) and \(\Sigma_{s=1}^{m+n-i}\beta_{s}\geq \gamma'(i)\). Therefore, there exist at least one \(r\in\{1,\dots,m+n-i\}\) such that \(\beta_{r}\geq a_{r}\) and \(w=(x_{1}^{\beta_{1}}\cdots x_{r}^{\beta_{r}-a_{r}}\cdots x_{m+n-i}^{\beta_{m+n-i}})x_{r}^{a_{r}}\in Q_{i_{\geq \gamma'(i)}}\) and the result follows.
By lemma 1, \(\text{Stab}_{d}(K_{n}\vee P_{m})=n+p\), so the corresponding elimination ideal is given as \(I_{D}(K_{n}\vee P_{m})=\bigcap\limits^{n+p}_{i=0}Q_{i}\), by proposition 1, \(I_{D}(K_{n}\vee P_{m})\) is stable for \(\gamma_{0}\), where \[\gamma_{0}=\max\{\gamma(i),\gamma'(j)|0\leq i\leq n-1 \ \text{and} \ n\leq j\leq n+p\}=n^{2}+2n(m-1)+m-1\] and by theorem 1, \(reg(I_{D}(K_{n}\vee P_{m}))\leq n^{2}+2n(m-1)+m-1.\)
Example 2. Consider \(K_{3}\vee P_{4},\) here \(n=3\) and \(m=4.\)
\(D(G_{0})=\{x_{1},x_{2},x_{3}\}\), \(Q_{0}=\langle x_{1}^{6},x_{2}^{6},x_{3}^{6},x_{4}^{5},x_{5}^{5},x_{6}^{4},x_{7}^{4}\rangle\) and \(reg(Q_{0})=30\), see Figure \(2\).
\(D(G_{1})=\{x_{1},x_{2}\}\), \(Q_{1}=\langle x_{1}^{5},x_{2}^{5},x_{3}^{4},x_{4}^{4},x_{5}^{3},x_{6}^{3}\rangle\) and \(reg(Q_{1})=19\), see Figure \(3\).
\(D(G_{2})=\{x_{1} \}\), \(Q_{2}=\langle x_{1}^{4},x_{2}^{3},x_{3}^{3},x_{4}^{2},x_{5}^{2}\rangle\) and \(reg(Q_{2})=10\), see Figure \(4\).
\(D(G_{3})=\{x_{1},x_{2} \}\), \(Q_{3}=\langle x_{1}^{2},x_{2}^{2},x_{3},x_{4}\rangle\) and \(reg(Q_{3})=3\), see Figure \(5\).
We recall the result about graphical degree stability of complete bipartite graph from [3]:
Proposition 4. Let \(K_{m,n}\) be a complete bipartite graph with \(m\geq n\) then:\[\text{Stab}_{d}(K_{m,n})=n-1\]
We generalize this result for complete \(n\)-partite graphs.
Lemma 1. Let \(K_{m_{1},\dots,m_{n}}\) be a complete n-partite graph with \(m_{i}\geq m_{j}\) for \(1\leq i<j\leq n\), then \[\text{Stab}_{d}(K_{m_{1},\dots,m_{n}})=m_{n}+m_{n-1}+\cdots+m_{2}-1\]
Proof. We prove it by induction. For \(n=2\), we have \(K_{m_{1},m_{2}}\) with \(m_{1}\geq m_{2}\) then by proposition 4: \[\text{Stab}_{d}(K_{m_{1},m_{2}})=m_{2}-1\] Let the result is true for \(n=k-1\), i.e. \[\text{Stab}_{d}(K_{m_{1},\dots,m_{k-1}})=m_{k-1}+m_{k-2}+\cdots+m_{2}-1\] with \(m_{i}\geq m_{j}\) if \(1\leq i<j\leq k-1\).
Consider \(G_{0}:=K_{m_{1},\dots,m_{k}}\), be the complete \(k-\)partite graph and \(V(G_{0})=X_{1}\cup X_{2}\cup\dots\cup X_{k}\), where each \(X_{r}=\{x_{r_{1}},x_{r_{2}},\dots,x_{r_{m_{r}}}\}\) is an independent set with \(|X_{r}|=m_{r}, \ 1\leq r\leq k\). Further \(m_{i}\geq m_{j}\) if \(1\leq i<j\leq k\).
If \(x\in X_{r}, \ 1\leq r\leq k\) then degree of \(x\) would be \(m_{1}+\cdots+m_{r-1}+m_{r+1}+\cdots+m_{k}.\) As \(m_{k}\leq m_{j}\) for all \(1\leq j\leq k-1,\) hence \(X_{k}\subseteq D(G_{0})\). So, without loss of generality we pick the vertex \(x_{k_{m_{k}}}\in X_{k}\), removing it will give us a new graph \(G_{1}\) with dominating set \(D(G_{1})=X_{k}-\{x_{k_{m_{k}}}\}\) with degree of each vertex of \(D(G_{1})\) is still \(m_{1}+\cdots+m_{k-1}\). If \(x\in X_{r}, \ 1\leq r\leq k-1\) then degree of \(x\) in \(G_{1}\) would be \(m_{1}+\cdots+m_{r-1}+m_{r+1}+\cdots+m_{k}-1\). Now pick \(x_{k_{m_{k-1}}}\) from \(D(G_{1})\) and remove it so that we get new graph \(G_{2}\) with dominating set \(D(G_{2})=X_{k}-\{x_{k_{m_{k}}},x_{k_{m_{k-1}}}\}\) with degree of each vertex of \(D(G_{2})\) is still \(m_{1}+\cdots+m_{k-1}.\) If \(x\in X_{r}, \ 1\leq r\leq k-1\) then degree of \(x\) in \(G_{2}\) would be \(m_{1}+\cdots+m_{r-1}+m_{r+1}+\cdots+m_{k}-2.\) Continue in this way we get \(G_{m_{k}}:=K_{m_{1},\dots,m_{k-1}}\). So, \[\text{Stab}_{d}(K_{m_{1},\ldots,m_{k}})=m_{k}+\text{Stab}_{d}(K_{m_{1},\dots,m_{k-1}})=m_{k}+m_{k-1}+\dots+m_{2}-1\] which completes the proof.
Corollary 1. Let \(K_{m,n}\) be a complete bipartite graph with \(m\geq n\), then the sequential ideal is given as follows: \[Q_{i}=\langle x_{1}^{m},\dots, x_{n-i}^{m},x_{n-i+1}^{n-i},\dots,x_{m+n-i}^{n-i}\rangle\] where \(0\leq i\leq n-1\).
Proof. The proof follows immediately from lemma 1.
Theorem 4. Let \(K_{m,n}\) be a complete bipartite graph with \(m\geq n\), then \[reg(I_{D}(K_{m,n}))\leq m+(2m-1)(n-1).\]
Proof. By proposition 4, \(\text{Stab}_{d}(K_{m,n})=n-1\). The sequential ideal is given as \(Q_{i}=\langle x_{1}^{a_{1}},\dots,x_{m+n-i}^{a_{m+n-i}}\rangle\) for all \(0\leq i\leq n-1\) where \[a_{j}=\begin{cases} m & if \ 1\leq j\leq n-i \\ n-i & if \ n-i+1\leq j\leq m+n-i. \end{cases}\] Let \(\gamma(i)=m+(2m-1)(n-i-1)\) for all \(0\leq i\leq n-1\), then we shall show that \(Q_{i_{\geq \gamma(i)}}\) is a stable ideal. Take \(u\in Q_{i_{\geq \gamma(i)}}\), then \(u=vx_{k}^{a_{k}}\) for some \(1\leq k\leq m+n-i\) where \(v\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)-a_{k}}\).
If \(m(u)>k,\) then \(\frac{x_{l}u}{x_{m(u)}}=\frac{x_{l}v}{x_{m(u)}}x_{k}^{a_{k}}\in Q_{i_{\geq \gamma(i)}}\) for all \(l<m(u)\). So, \(Q_{i_{\geq \gamma(i)}}\) is stable.
If \(m(u)=k,\) then clearly \(u\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\) and \(Q_{i_{\geq \gamma(i)}}\subseteq\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\). We are to show that \(\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\subseteq Q_{i_{\geq \gamma(i)}}\). Let \(w\in\langle x_{1},\dots,x_{m+n-i}\rangle^{\gamma(i)}\) then \(w=x_{1}^{\beta_{1}}x_{2}^{\beta_{2}}\cdots x_{m+n-i}^{\beta_{m+n-i}}\) with \(\beta_{s}\geq0\) for all \(1\leq s\leq m+n-i\) and \(\Sigma_{s=1}^{m+n-i}\beta_{s}\geq \gamma(i)\). Therefore, there exist at least one \(r\in\{1,\dots,m+n-i\}\) such that \(\beta_{r}\geq a_{r}\) and \(w=(x_{1}^{\beta_{1}}\cdots x_{r}^{\beta_{r}-a_{r}}\cdots x_{m+n-i}^{\beta_{m+n-i}})x_{r}^{a_{r}}\in Q_{i_{\geq \gamma(i)}}\) and the result follows.
By proposition 1, \(I_{D}(K_{m,n})=\bigcap\limits^{n-1}_{i=0}Q_{i}\) is stable for \(\gamma_{0}\), where \[\gamma_{0}=\max\{\gamma(i)|0\leq i\leq n-1\}=m+(2m-1)(n-1)\] and by theorem 1, \(reg(I_{D}(K_{m,n}))\leq m+(2m-1)(n-1).\)
Example 3. Consider \(K_{4,3},\) here \(m=4\) and \(n=3.\)
\(D(G_{0})=\{x_{1},x_{2},x_{3}\}\),
\(Q_{0}=\langle
x_{1}^{4},x_{2}^{4},x_{3}^{4},x_{4}^{3},x_{5}^{3},x_{6}^{3},x_{7}^{3}\rangle\)
and \(reg(Q_{0})=18\), see Figure \(6\).
\(D(G_{1})=\{x_{1},x_{2}\}\), \(Q_{1}=\langle x_{1}^{4},x_{2}^{4},x_{3}^{2},x_{4}^{2},x_{5}^{2},x_{6}^{2}\rangle\) and \(reg(Q_{1})=11\),see Figure \(7\).
\(D(G_{2})=\{x_{1}\}\), \(Q_{2}=\langle x_{1}^{4},x_{2},x_{3},x_{4},x_{5}\rangle\) and \(reg(Q_{2})=4\), see Figure \(8\).
Remark 3. As elimination ideals are of Borel type ideals and an upper bound for Borel type ideal were discussed in [2] and [1]. It is worthy to note that our given bounds are sharper than the one given in [2] and [7].
The first and second authors were supported by the Higher Education Commission (Islamabad) through the National Research Program for Universities, Grant No.7359/Punjab/NRPU/R\(\&\)D/ HEC/ 2017.
The author declares no conflict of interests.