# Certain Bounds of Regularity of Elimination Ideals on Operations of Graphs

Authors: Zongming Lv; Muhammad Junaid Ali Junjua; Muhammad Tajammal Tahir; Khurram Shabbir
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Elimination ideals are regarded as a special type of Borel type ideals, obtained from degree sequence of a graph, introduced by Anwar and Khalid. In this paper, we compute graphical degree stabilities ofKn∨Cm and Kn∗Cm by using the DVE method. We further compute sharp upper bound for Castelnuovo–Mumford regularity of elimination ideals associated to these families of graphs.


---

## Body

## 1. Introduction

LetS=kx1,…,xn, n≥2 be a polynomial ring in n variables over an infinite field k. Bayer and Stillman (see [1]) noted that a monomial ideal I⊂S is of Borel type, if it satisfies the following condition:(1)I:xj∞=I:x1,…,xj∞,for all1≤j≤n.The Castelnuovo–Mumford regularity (or simply regularity) gives an estimate of the complexity of computing Gro..bner bases. The regularity of an ideal I is defined as regI=maxj:βi,i+jI≠0, where βij’s are the graded Betti numbers of ideal I. The regularity of monomial ideals of Borel type was extensively studied (see for instance [2–4]).The study of degree sequence started in 1981 by Bollobas [5]. Tyshkevich et al. in [6] established a correspondence between degree sequence of a graph and some structural properties of this graph. Havel–Hakimi criterion (see [7]) states that a sequence d1,d2,…,dn of non-negative integers such that d1≥d2≥⋯≥dn is graphic if and only if the sequence d2−1,…,dd1+1−1,dd1+2,…,dn is graphic. Given a non-negative sequence d1,d2,…,dn, this sequence will be called realizable if it is a degree sequence of any graph.Throughout this paper, we assumeH to be a simple, finite, and connected graph and label its vertices according to the degree sequence in descending order. In figures, we identify the vertex vi of H with the positive integer i. Further, we identify a vertex vi of a graph H with variable xi of the polynomial ring S=kx1,…,xn. Recently, Anwar and Khalid in [2] introduced a new class of monomial ideals, namely, elimination ideals IDH, associated to a graph H. They showed that elimination ideals are the monomial ideals of Borel type. They gave the description of graphical degree stability of graph H denoted by StabdH, a combinatorial measure associated to H. They gave a systematic procedure to compute the graphical degree stability, namely, dominating vertex elimination method (DVE method). In [2, 8], the authors computed the upper bounds of the Castelnuovo–Mumford regularity of elimination ideals associated to some families of graphs [9–11].Motivated by the studies in [2, 8], we further extend this study for join and corona product of complete and cyclic graphs. We compute the graphical degree stabilities of join and corona product of above graphs by using the dominating vertex elimination method (see Lemmas 1 and 2). We give a description on computing the sharp upper bounds for the regularity of elimination ideals associated to these families of graphs respectively (see Theorems 1 and 2).


## 2. Preliminaries

Definition 1.
LetH be a simple, finite, and connected graph with vertex set VH. The degree of a vertex v∈VH, denoted by dv, is the number of edges at v.
A vertexvi of a graph H is called dominating vertex, if degvi≥degvj for all vj∈VH with i≠j. The set of all dominating vertices of a graph H is called dominating set and is denoted by DH. A graph H is called scattered graph if it has at least one vertex with degree zero; otherwise, it is called non-scattered graph.Here, we introduce different operations on graphs.Definition 2.
LetG and H be two graphs with mutually disjoint vertex sets VG=u1,u2,…,un and VH=v1,v2,…,vm. A graph denoted by G∨H is called the join of G and H if VG∨H=VG∪VH and EG∨H=EG∪EH∪uivj|ui∈VG,vj∈VH.Definition 3.
The corona product of two graphsG and H is the graph obtained by taking one copy of G and VG disjoint copies of H and then joining the jth vertex of G to every vertex in the jth copy of H. We denote this graph as G∗H. Corona product of two graphs G and H with n and m vertices, respectively, has n+nm vertices.Definition 4.
LetHi be a graph and pick a vertex x∈DHi such that Hi+1=Hi−x is an induced, non-scattered subgraph of Hi. This method of obtaining an induced, non-scattered subgraph Hi+1 from Hi by eliminating a vertex from the dominating set DHi is called the dominating vertex elimination method (DVE method) (see [2] for more details). Let H be a simple finite and connected graph; then, the length of the maximum chain of induced, non-scattered, subgraphs of H obtained by successively applying DVE method is called graphical degree stability and is denoted as StabdH. In other words, if H=H0⊃H1⊃⋯⊃Hr is the maximum chain of induced, non-scattered, subgraphs of H obtained by using DVE method, then StabdH. Note that the vertex set of Hj consists of n−j vertices where 1≤j≤r.Definition 5.
LetH be a simple, finite, and connected graph with vertex set VH=x1,x2,…,xn having degree sequence of vertices d1,d2,…,dn such that d1≥d2≥⋯≥dn and di≥0,∀1≤i≤n; then, the ideal QH=x1d1,x2d2,…,xndn is called the sequential ideal associated to the graph H. Let H=H0⊃H1⊃⋯⊃Hr be the maximum chain of induced, non-scattered, subgraphs of H obtained by using the DVE method with StabdH=r and QHi=x1di1,x2di2,…,xn−idin−i be the sequential ideal corresponding to Hi, 0≤i≤r; then, the elimination ideal of H is defined as(2)IDH=QH0∩QH1∩⋯∩QHr.LetS=Kx1,x2,…,xn, n≥2, be a polynomial ring over infinite field K and I⊆S be a monomial ideal of S. Let GI be the minimal set of monomial generators of I and the highest degree of monomial in GI is denoted as degI. Also, let I≥t be an ideal generated by monomial of I of degree ≥t. Given a monomial u∈S, set mu=maxi:xi|u and mI=maxu∈GImu. A monomial ideal I is stable if for any u∈GI we have xi.u/xmu∈I for all 1≤i<mu.Eisenbud et al. proved the following result in [12].Proposition 1.
LetI be a monomial ideal such that I≥e is stable, where e≥degI is an integer. Then, regI≤e.Remark 1.
LetI and J are two monomial ideals with r≥degI and s≥degJ, where r and s are two integers such that I≥r and J≥s are stable ideals; then, I∩J≥maxr,s is stable ideal.


## 3. Regularity ofKn∨Cm

In this section, we present our results regarding the Castelnuovo–Mumford regularity of elimination ideals associated to join operation of complete graph and cyclic graph.In [2], the authors gave the following formula to compute the graphical degree stability for cyclic graphs.Proposition 2.
IfCm,m≥3, is the cyclic graph, then(3)StabdCm=m3,ifm≡0mod3,m−13,ifm≡1mod3,m−23,ifm≡2mod3.Lemma 1.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph; then,(4)StabdKn∨Cm=n+StabdCm.Proof.
We shall prove it by induction onn. Let n=2; then, H0=K2∨Cm with degree sequence(5)m+1,m+1,4,…,4︸m−tuple,and DH0=x1,x2. Without loss of generality, pick x1∈DH0, and using the DVE method, we get H1 with the degree sequence (always rearrange the sequence after applying DVE method) m,3,…,3︸m−tuple and DH1=x1. Again applying the DVE method, we get H2=Cm. So, StabdK2∨Cm=2+StabdCm. Suppose that result is true for n=p; then, the degree sequence Kp∨Cm will be(6)p+m−1,…,p+m−1︸p−tuple,p+2,…,p+2︸m−tuple,StabdKp∨Cm=p+StabdCm.
Considern=p+1; then, H0=Kp+1∨Cm with degree sequence(7)p+m,…,p+m︸p+1−tuple,p+3,…,p+3︸m−tuple,and VH0=p+m+1, with DH0=x1,…,xp+1 as m≥4 which are precisely the vertices that initially belonged to Kp+1. Without loss of generality, pick x1∈DH0, and applying the DVE method, we get H1=Kp∨Cm.(8)⇒StabdKp+1∨Cm=1+StabdKp∨Cm=1+p+StabdCm=1+p+StabdCm,⇒StabdKp+1∨Cm=p+1+StabdCm.Corollary 1.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph; then, the sequential ideal of Kn∨Cm is given as(9)Qi=x1n+m−i−1,…,xn−in+m−i−1,xn−i+1n−i+2,…,xn+m−in−i+2,0≤i≤n,x12,…,xm−3i−n2,xm−3i−n+1,…,xn+m−i,n+1≤i≤n+StabdCm.Proof.
This proof is immediate from Lemma1.Proposition 3.
LetKn∨Cm,n≥2andm≥4, be the join of complete and cyclic graphs, respectively, and(10)Qi=x1n+m−i−1,…,xn−in+m−i−1,xn−i+1n−i+2,…,xn+m−in−i+2be the sequential ideal associated to Hi; then, Qi≥γi is stable ideal, where γi=n−i2+m2n−2i+1+2i−n+1 and 0≤i≤n.Proof.
LetH0=Kn∨Cm,n≥2andm≥4, be the join of complete and cyclic graphs, respectively; then, by Corollary 1, sequential ideal associated to Hi,0≤i≤n, is given as Qi=x1a1,…,xn+m−ian+m−i where(11)ak=n+m−i−1,1≤k≤n−i,n−i+2,n−i+1≤k≤n+m−i.
Letγi=n−i2+m2n−2i+1+2i−n+1, for all 0≤i≤n. We shall show that Qi≥γi is a stable ideal. Take u∈Qi≥γi; then, u=vxkak for some 1≤k≤n+m−i where v∈x1,…,xn+m−iγi−ak.
Ifmu>k, then xlu/xmu=xlv/xmuxkak∈Qi≥γi for all l<mu. So, Qi≥γi is stable.
Ifmu=k, then clearly u∈x1,…,xn+m−iγi.(12)⇒Qi≥γi⊆x1,…,xn+m−iγi.
We show thatx1,…,xn+m−iγi⊆Qi≥γi. Let w∈x1,…,xn+m−iγi; then, w=x1β1x2β2,…,xn+m−iβn+m−i with βs≥0 for all 1≤s≤n+m−i and ∑s=1n+m−iβs≥γi. Therefore, there exists at least one s∈1,…,n+m−i such that βs≥as and w=x1β1,…,xsβs−as,…,xn+m−iβn+m−ixsas∈Qi≥γi, and the result follows.Proposition 4.
LetKn∨Cm,n≥2andm≥4, be the join of complete and cyclic graphs, respectively, and(13)Qi=x12,…,xm−3i−n2,xm−3i−n+1,…,xn+m−ibe the sequential ideal associated to Gi,n+1≤i≤n+StabdCm; then, Qi≥γi is stable ideal, where γi=m+3n−3i+1.Proof.
LetH0=Kn∨Cm,n≥2andm≥4, be the join of complete and cyclic graphs, respectively; then, by Corollary 1, sequential ideal associated to Hi,n+1≤i≤n+StabdCm, is given as Qi=x1a1,…,xn+m−ian+m−i where(14)ak=2,1≤k≤m−3i−n,1,m−3i−n+1≤k≤n+m−i.
Letγi=m+3n−3i+1, for all n+1≤i≤n+StabdCm; then, by similar arguments as above, Qi≥γi is a stable ideal.Theorem 1.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph. Then, regIDKn∨Cm≤n2+m2n+1−2n+1.Proof.
IfStabdCm=p, then by using Proposition 2, StabdKn∨Cm=n+p, so the corresponding elimination ideal is given as IDKn∨Cm=∩i=0n+pQi, and by using Propositions 3 and 4 and Remark 1, IDKn∨Cm is stable for γ, where(15)γ=maxγi,|0≤i≤n+p=n2+m2n+1−2n+1.
By using Proposition1,(16)regIDKn∨Cm≤n2+m2n+1−2n+1.Example 1.
ConsiderK2∨C4, where n=2 and m=4 (see Figure 1).DH0=x1,x2, Q0=x15,x25,x34,x44,x54,x64, and regQ0=21.DH1=x1, Q1=x14,x23,x33,x43,x53, and regQ1=12.DH2=x1,x2,x3,x4, Q2=x12,x22,x32,x42, and regQ2=5.DH3=x1, Q3=x12,x2,x3, and regQ3=2.Figure 1
H0,H1,H2,H3.Remark 2.
In general,Qi≥γi−1 is not stable, where Qi are sequential ideals of Kn∨Cm,where0≤i≤n+StabdCm. As in Example 1, Q1≥11 is not a stable ideal for i=1andγ1=12.


## 4. Regularity ofKn∗Cm

In this section, we present our results concerning the Castelnuovo–Mumford regularity of elimination ideals associated to corona product operation of complete graph and cyclic graphs.Lemma 2.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph; then,(17)StabdKn∗Cm=n+nStabdCm.Proof.
We shall prove it by induction onn. Let n=2; then, H0=K2∗Cm with degree sequence(18)m+1,m+1,3,…,3︸m−tuple,3,…,3︸m−tuple,and DH0=x1,x2. Without loss of generality, pick x1∈DH0, and using the DVE method, we get H1 with the degree sequence(19)m,3,…,3︸m−tuple,2,…,2︸m−tuple.
NowDH1=x1, and again applying the DVE method, we have only two copies of Cm in H2 with degree sequence(20)2,…,2︸m−tuple,2,…,2︸m−tuple,⇒StabdK2∗Cm=2+2StabdCm.
Suppose that result is true forn=p; then, the degree sequence of Kp∗Cm will be(21)p+m−1,…,p+m−1︸p−tuple,3,…,3︸m−tuple,…,3,…,3︸m−tuple︸pm−tuple,⇒StabdKp∗Cm=p+pStabdCm.
Considern=p+1; then, H0=Kp+1∗Cm with degree sequence(22)p+m,…,p+m︸p+1−tuple,3,…,3︸m−tuple,…,3,…,3︸m−tuple︸mp+1−tuple,and VH0=pm+p+m+1 with DH0=x1,…,xp+1 which are precisely the vertices that initially belonged to Kp+1 because m≥4. By applying the DVE method, we get Kp∗Cm and one copy of Cm, and we call this graph H1.(23)⇒StabdKp+1∗Cm=1+StabdKp∗Cm+StabdCm=1+p+pStabdCm+StabdCm,⇒StabdKp+1∗Cm=p+1+p+1StabdCm.Corollary 2.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph; then, the sequential ideal of Kn∗Cm is given as(24)Qi=x1n+m−1,…,xnn+m−1,xn+13,…,xr3,i=0,x1n+m−i−1,…,xn−in+m−i−1,xn−i+13,…,xr−im+13,xr−im+1+12,…,xr−i2,1≤i≤n−1,x12,…,xnm2,i=n,x12,…,xnm−3i−n2,xnm−3i−n+1,…,xr−i,n+1≤i≤n+nStabdCm,where r=n+nmProof.
The proof is immediate from Lemma2.Proposition 5.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively, and(25)Q0=x1n+m−1,…,xnn+m−1,xn+13,…,xr3,be the sequential ideal associated to H0; then, Q0≥γ0 is stable ideal, where r=n+nm and γ0=n2+n3m−2+1.Proof.
LetH0=Kn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively; then, by Corollary 2, the sequential ideal associated to H0 is given as Q0=x1a1,…,xrar where(26)aj=n+m−1,1≤j≤n,3,n+1≤j≤r.
Letγ0=n2+n3m−2+1. We show that Q0≥γ0 is a stable ideal. Take u∈Q0≥γ0; then, u=vxkak for some 1≤k≤r where v∈x1,…,xrγ0−ak.
Ifmu>k, then xlu/xmu=xlv/xmuxkak∈Q0≥γ0 for all l<mu. So, Q0≥γ0 is stable.
Ifmu=k, then clearly u∈x1,…,xrγ0.(27)⇒Q0≥γ0⊆x1,…,xrγ0.
We show thatx1,…,xrγ0⊆Q0≥γ0. Let w∈x1,…,xrγ0; then, w=x1β1x2β2⋯xrβr with βs≥0 for all 1≤s≤r and ∑s=1rβs≥γ0. Therefore, there exists at least one s∈1,…,r such that βs≥as and w=x1β1,…,xsβs−as,…,xrβrxsas∈Q0≥γ0, and the result follows.Proposition 6.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively, and(28)Qi=x1n+m−i−1,…,xn−in+m−i−1,xn−i+13,…,xr−im+13,xr−im+1+12,…,xr−i2,be the sequential ideal associated to Hi; then, Qi≥γi is stable ideal, where r=n+nm,γi=n−i2−2n+mi−i+3nm+1 and 1≤i≤n−1.Proof.
LetH0=Kn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively; then, by Corollary 2, sequential ideal associated to Hi,1≤i≤n−1, is given as Qi=x1a1,…,xr−iar−i where(29)aj=n+m−i−1,1≤j≤n−i,3,n−i+1≤j≤r−im+1,2,r−im+1+1≤j≤r−i.
Letγi=n−i2−2n+mi−i+3nm+1, for all 1≤i≤n−1. We shall show that Qi≥γi is a stable ideal. Take u∈Qi≥γi; then, u=vxkak for some 1≤k≤r−i where v∈x1,…,xr−iγi−ak.
Ifmu>k, then xlu/xmu=xlv/xmuxkak∈Qi≥γi for all l<mu. So, Qi≥γi is stable.
Ifmu=k, then clearly u∈x1,…,xr−iγi.(30)⇒Qi≥γi⊆x1,…,xr−iγi.
We show thatx1,…,xr−iγi⊆Qi≥γi. Let w∈x1,…,xr−iγi; then, w=x1β1x2β2,…,xr−iβr−i with βs≥0 for all 1≤s≤r−i and ∑s=1r−iβs≥γi. Therefore, there exists at least one s∈1,…,r−i such that βs≥as and w=x1β1,…,xsβs−as,…,xr−iβr−ixsas∈Qi≥γi, and the result follows.Proposition 7.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively, and Qn=x12,…,xnm2 be the sequential ideal associated to Hn; then, Qn≥γn is stable ideal, where r=n+nm and γn=nm+1.Proof.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively; then, by Corollary 2, sequential ideal associated to Hn is given as Qn=x12,…,xnm2. Let γn=nm+1; then, by similar arguments as above, Qn≥γn is a stable ideal.Proposition 8.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively, and(31)Qi=x12,…,xnm−3i−n2,xnm−3i−n+1,…,xr−i,be the sequential ideal associated to Hi; then, Qi≥γi is stable ideal, where r=n+nm,γi=nm+3n−i+1, and n+1≤i≤n+nStabdCm.Proof.
LetKn∗Cm,n≥2andm≥4, be the corona product of complete and cyclic graphs, respectively; then, by Corollary 2, sequential ideal associated to Hi,n+1≤i≤n+nStabdCm, is given as Qi=x1a1,…,xr−iar−i, where(32)aj=2,1≤j≤nm−3i−n,1,nm−3i−n+1≤j≤r−i.
Letγi=nm+3n−i+1, for all n+1≤i≤n+nStabdCm. We shall show that Qi≥γi is a stable ideal. Take u∈Qi≥γi; then, u=vxkak for some 1≤k≤r−i where v∈x1,…,xr−iγi−ak.
Ifmu>k, then xlu/xmu=xlv/xmuxkak∈Qi≥γi for all l<mu. So, Qi≥γi is stable.
Ifmu=k, then clearly u∈x1,…,xr−iγi.(33)⇒Qi≥γi⊆x1,…,xr−iγi.
We show thatx1,…,xr−iγi⊆Qi≥γi. Let w∈x1,…,xr−iγi; then, w=x1β1x2β2,…,xr−iβr−i with βs≥0 for all 1≤s≤r−i and ∑s=1r−jβs≥γi. Therefore, there exists at least one s∈1,…,r−i such that βs≥as and w=x1β1,…,xsβs−as,…,xr−iβr−ixsas∈Qi≥γi, and the result follows.Theorem 2.
LetKn,n≥2, be a complete graph and Cm,m≥4, be a cyclic graph; then, we have(34)regIDKn∗Cm≤n2+n3m−2+1.Proof.
IfStabdCm=p, then by using Proposition 2, StabdKn∗Cm=n+np, so the corresponding elimination ideal is given as IDKn∗Cm=∩i=0n+npQi, and by using Propositions 5–8 and Remark 1, IDKn∗Cm is stable for γ, where(35)γ=maxγi|0≤i≤n+np=n2+n3m−2+1.
By using Proposition1,(36)regIDKn∗Cm≤n2+n3m−2+1.Example 2.
ConsiderK2∗C4, where n=2 and m=4 (see Figure 2).DH0=x1,x2, Q0=x15,x25,x33,x43,x53,x63,x73,x83,x93,x103, and regQ0=25.DH1=x1, Q1=x14,x23,x33,x43,x53,x62,x72,x82,x92, and regQ1=16.DH2=x1,x2,x3,x4,x5,x6,x7,x8, Q2=x12,x22,x32,x42,x52,x62,x72,x82, and regQ2=9.DH3=x1,x2,x3,x4,x5, Q3=x12,x22,x32,x42,x52,x6,x7, and regQ3=6.DH4=x1,x2, Q4=x12,x22,x3,x4,x5,x6, and regQ4=3.Figure 2
H0,H1,H2,H3,H4.Remark 3.
In general, one cannot getQi≥γi−1 stable, where Qi are the sequential ideals of Kn∗Cm,0≤i≤n+nStabdCm. As in Example 2, for i=2γ2=9 and Q2≥8 is not a stable ideal.Remark 4.
Elimination ideals are Borel type ideals, and upper bound for Borel type ideals was discussed in [3, 13]; it is worthy to note that our given bounds are sharper than the ones given in [3, 13].



---

*Source: 3697430-2021-10-29.xml*