You are an expert at summarizing long articles. Proceed to summarize the following text: 
castelnuovo - mumford regularity ( or just the regularity ) is something of a two - way study in the sense that it is a fundamental invariant both in commutative algebra and discrete geometry . the regularity is a kind of universal bound for measuring the complexity of a considered object ( a module , a sheaf or a simplicial complex ) . our interest here is to compute or provide better bounds for the regularity of rings associated to graphs . we are primarily concerned on the computation of the regularity of the edge ring ( or equivalently the stanley - reisner ring of the independence complex ) of a given graph . one way to attack such a problem goes by translating the underlying algebraic or topological language to that of graph s . such an approach may enable us to bound the regularity of a graph via other graph parameters , and the most likely candidate is the induced matching number . by a theorem of katzman  @xcite , it is already known that the induced matching number provides a lower bound for the regularity of a graph , and the characterization of graphs in which the regularity equals to the induced matching number has been the subject of many recent papers  @xcite .    during his search on the complexity of the induced matching number , lozin  @xcite describes an operation ( he calls it as the _ stretching operation _ ) on graphs , and he proves that when it is applied to a graph , the induced matching number increases exactly by one . his operation works simply by considering a vertex @xmath0 of a graph @xmath1 whose ( open ) neighborhood splitted into two disjoint parts @xmath2 , and replacing the vertex @xmath0 with a four - path on @xmath3 together with edges @xmath4 for any @xmath5 and @xmath6 ( see section  [ section : reg - lozin ] ) . one of the interesting results of his work is that the induced matching problem remains @xmath7-hard in a narrow subclass of bipartite graphs . we here prove that his operation has a similar effect on the regularity :    [ thm : lozin+reg ] let @xmath8 be a graph and let @xmath9 be given . then @xmath10 , where @xmath11 is the lozin s transform of @xmath1 with respect to the vertex @xmath0 . theorem  [ thm : lozin+reg ] implies that the computational complexity of the regularity of arbitrary graphs is equivalent to that of bipartite graphs having sufficiently large girth with maximum degree three . one of the main advantages of theorem  [ thm : lozin+reg ] is that we are able to prove that the regularity of any graph can be bounded above by a function of its induced matching number . moreover , we also show that the regularity of a graph is always less than or equal to the sum of its induced matching and decycling numbers . we further employ the language of graph coloring theory by introducing a gallai type graph  @xcite associated to any given graph in order to describe a new class of graphs in which the regularity equals to the induced matching number . the organization of the paper is as follows . in section @xmath12 , we fix our notations needed throughout , recall definitions and basic properties of the regularity of simplicial complexes and graphs . the section @xmath13 is devoted to the proof of theorem  [ thm : lozin+reg ] , where we also analyze the topological effect of lozin s transformation on the independence complexes of graphs . in the final section , we provide various bounds on the regularity as promised . let @xmath14 be a simplicial complex on the vertex set @xmath15 , and let @xmath16 be any field . then the _ castelnuovo - mumford regularity _ ( or just the _ regularity _ ) @xmath17 of @xmath14 over @xmath16 is defined by @xmath18;{\bbbk})\neq 0\;\textrm{for\;some}\;s\subseteq v\},\ ] ] where @xmath19:=\{f\in { \delta}\colon f\subseteq s\}$ ] is the induced subcomplex of @xmath14 by @xmath20 , and @xmath21 denotes the ( reduced ) singular homology . note that this definition of the regularity coincides with the algebraic one via the well - known hochster s formula . some of the immediate consequences of the above definition are as follows . firstly , the regularity is dependent on the characteristic of the coefficient field ( compare example @xmath22 of @xcite ) . secondly , it is not a topological invariant , and it is monotone decreasing with respect to the induced subcomplex operation , that is , @xmath23)\leq { \textrm{reg}}_{{\bbbk}}({\delta})$ ] for any @xmath24 . in most cases , our results are independent of the choice of the coefficient field , so we drop @xmath16 from our notation .    even if the regularity is not a topological invariant , the use of topological methods plays certain roles . in many cases , we will appeal to an induction on the cardinality of the vertex set by a particular choice of a vertex accompanied by two subcomplexes . to be more explicit , if @xmath0 is a vertex of @xmath14 , then the subcomplexes @xmath25 and @xmath26 are called the _ deletion _ and _ link _ of @xmath0 in @xmath14 respectively . such an association brings the use of a mayer - vietoris sequence of the pair @xmath27 : @xmath28    [ prop : induction - sc ] let @xmath14 be a simplicial complex and let @xmath9 be given . then @xmath29    suppose that @xmath30 , and let @xmath31 be a subset for which @xmath32)\neq 0 $ ] . if @xmath33 , then @xmath34 so that @xmath35 , that is , @xmath36 . therefore , we may assume that @xmath37 . we set @xmath38 $ ] , @xmath39 $ ] and @xmath40 $ ] , and consider the mayer - vietoris sequence of the pair @xmath41 : @xmath42 observe that @xmath43 and @xmath44 . now , if @xmath45 , then @xmath46 so that @xmath47 , since @xmath48 by our assumption . thus , @xmath49 . this proves the claim . we next review some necessary terminology from graph theory . by a graph @xmath8 , we will mean an undirected graph without loops or multiple edges . an edge between @xmath50 and @xmath51 is denoted by @xmath52 or @xmath53 interchangeably . a graph @xmath8 is called an _ edgeless graph _ on @xmath15 whenever @xmath54 . if @xmath55 , the graph induced on @xmath56 is written @xmath57 $ ] , and in particular , we abbreviate @xmath58 $ ] to @xmath59 , and write @xmath60 whenever @xmath61 . in a similar vein , we denote by @xmath62 the graph on @xmath15 having the edge set @xmath63 whenever @xmath64 . the _ complement _ @xmath65 of a graph @xmath8 is the graph on @xmath15 with @xmath66 if and only if @xmath67 . throughout @xmath68 , @xmath69 and @xmath70 will denote the complete , cycle and path graphs on @xmath71 vertices respectively . given two nonempty graphs @xmath72 and @xmath73 on disjoint sets , then their _ disjoint union _ @xmath74 is defined to be the graph @xmath75 .    for a given subset @xmath76 , the ( open ) neighborhood of @xmath56 is defined by @xmath77 , where @xmath78 , and similarly , @xmath79:=n_g(u)\cup u$ ] is the closed neighborhood of @xmath56 . furthermore , if @xmath80 is a subset of edges of @xmath1 , we write @xmath81 $ ] for the set @xmath82 $ ] , where @xmath83 is the set of vertices incident to edges in @xmath84 . a subset @xmath85 is called an _ independent set _ whenever @xmath86 $ ] is an edgeless graph . the set of all independent sets of @xmath1 forms a simplicial complex @xmath87 , the _ independence complex _ of @xmath1 . the largest cardinality of an independent set in @xmath1 is called the _ independence number _ of @xmath1 and denoted by @xmath88 . let @xmath1 be a graph . regularity _ of @xmath1 is defined by @xmath89 .    when considering the complex @xmath87 , the deletion and link of a given vertex @xmath0 correspond to the independence complexes of induced subgraphs , namely that @xmath90 and @xmath91)$ ] . therefore , the following is an immediate consequence of proposition  [ prop : induction - sc ] , which is also proven in algebraic setting in  @xcite . [ cor : induction - sc ] let @xmath1 be a graph and let @xmath92 be given . then @xmath93)+1\}.\ ] ]    we say that @xmath1 is @xmath94-free if no induced subgraph of @xmath1 is isomorphic to @xmath94 . a graph @xmath1 is called _ chordal _ if it is @xmath95-free for any @xmath96 , and a graph is said to be _ cochordal _ if its complement is a chordal graph . a subset @xmath97 is called a _ complete _ of @xmath1 if @xmath98 $ ] is isomorphic to a complete graph , and the largest cardinality of a complete of @xmath1 is called the _ clique number _ of @xmath1 and denoted by @xmath99 . recall that a subset @xmath100 is called a _ matching _ of @xmath1 if no two edges in @xmath101 share a common end . moreover , a matching @xmath101 of @xmath1 is an _ induced matching _ if it occurs as an induced subgraph of @xmath1 , and the cardinality of a maximum induced matching is called the _ induced matching number _ of @xmath1 and denoted by @xmath102 . let @xmath1 be a graph , and @xmath103 be a family of graphs . the @xmath103-_cover number _ of @xmath1 is the minimum number of subgraphs @xmath104 of @xmath1 such that every @xmath105 and @xmath106 . in particular , we denote by @xmath107 , the _ cochordal cover number _ of @xmath1 ( see  @xcite ) . [ thm : im - reg - cd ] the inequality @xmath108 holds for any graph @xmath1 . both bounds are far from being tight even for connected graphs . we have constructed in  @xcite a connected graph @xmath109 for each @xmath110 such that @xmath111 ( see proposition 3.12 of  @xcite ) . for the lower bound , let @xmath112 be the graph obtained from @xmath113 disjoint five cycles by adding an extra vertex and connecting it to exactly one vertex of each five cycle ( see figure  [ fig - reg - im-1 ] ) . then the equality @xmath114 for any @xmath110 follows from corollary  [ cor : induction - sc ] . .,width=297,height=96 ]    the graph @xmath112 is also interesting for one other reason that we explain next . a vertex @xmath0 of @xmath1 is called a _ shedding vertex _ if for every independent set @xmath20 in @xmath115 $ ] , there is some vertex @xmath116 so that @xmath117 is independent . a graph @xmath1 is called _ vertex decomposable _ if either it is an edgeless graph or it has a shedding vertex @xmath0 such that @xmath60 and @xmath115 $ ] are both vertex - decomposable . [ thm : vd - reg ] if @xmath1 is a @xmath118-free vertex decomposable graph , then @xmath119 . the bounds of theorem  [ thm : im - reg - cd ] can be tight if the graph lies in a specific graph class . [ prop : chordal - reg ] if @xmath1 is a chordal graph , then @xmath120 . the existence of vertices satisfying some extra properties is useful when dealing with the homotopy type of the independence complexes of graphs . [ thm : hom - induction ] if @xmath121 , then there is a homotopy equivalence @xmath122 . on the other hand , if @xmath123\subseteq n_g[v]$ ] , then the homotopy equivalence @xmath124)$ ] holds , where @xmath125 denotes the ( unreduced ) suspension of @xmath126 . an edge @xmath53 is called an _ isolating edge _ of @xmath1 with respect to a vertex @xmath127 , if @xmath127 is an isolated vertex of @xmath128 $ ] . [ thm : isolating ] if @xmath129)$ ] is contractible , then the natural inclusion @xmath130 is a homotopy equivalence .    in particular , theorem  [ thm : isolating ] implies that @xmath131 whenever the edge @xmath132 is isolating . this brings the use of an operation , adding or removing an edge , on a graph without altering its homotopy type . we will follow @xcite to write @xmath133 ( respectively @xmath134 ) to indicate that we add the edge @xmath135 to ( resp . remove the edge @xmath135 from ) the graph @xmath1 , where @xmath127 is the corresponding isolated vertex . this section is devoted to the proof of theorem  [ thm : lozin+reg ] . we begin with recalling the definition of the lozin s transformation on graphs  @xcite . let @xmath8 be a graph and let @xmath9 be given . lozin s transform _ @xmath11 of @xmath1 with respect to the vertex @xmath0 is defined as follows :    * partition the neighborhood @xmath136 of the vertex @xmath0 into two subsets @xmath137 and @xmath138 in arbitrary way ; + * delete vertex @xmath0 from the graph together with incident edges ; + * add a @xmath139 to the rest of the graph ; + * connect vertex @xmath140 of the @xmath141 to each vertex in @xmath137 , and connect @xmath142 to each vertex in @xmath138 . when the decomposition @xmath143 is of importance , we will write @xmath144 instead of @xmath11 . it should be noted that we allow one of the sets @xmath137 and @xmath138 to be an empty set . furthermore , if @xmath0 is an isolated vertex , the corresponding lozin s transform of @xmath1 with respect to the vertex @xmath0 is the graph @xmath145 . throughout we will follow the convention made in  @xcite to use special notations for some particular classes of graphs : + @xmath146 , the class of @xmath147-free graphs , + @xmath148 , the class of @xmath149-free graphs , + @xmath150 , the class of graphs with maximum degree @xmath13 , + @xmath151 , the class of bipartite graphs , + where the graph @xmath152 is depicted in figure  [ fig - h ] . .,width=240,height=76 ]    lozin proves in @xcite that his transformation increases the induced matching number exactly by one . [ lem : lozin - inmatch ] for any graph @xmath1 and any vertex @xmath153 , the equality @xmath154 holds . furthermore , any graph can be transformed by a sequence of lozin transformations into a graph in class @xmath155 with any integer @xmath156 and @xmath157 . we next prove that the lozin s transformation has a similar effect on the regularity . in order to simplify the notation , we note that when we mention the homology or homotopy of a graph , we mean that of its independence complex , so whenever it is appropriate , we drop @xmath158 from our notation . [ prop : reg+isolating ] let @xmath53 be an isolating edge of @xmath94 with respect to the vertex @xmath127 . if @xmath127 has a neighbor @xmath0 of degree two , then @xmath159 .    without loss of generality , we may assume that @xmath160 . we let @xmath161 , and assume that @xmath162 . let @xmath163 be a subset satisfying @xmath164)\neq 0 $ ] . we suppose that @xmath20 is maximal in the sense that @xmath165)=0 $ ] for any @xmath166 . if @xmath167 or @xmath168 , we clearly have @xmath169\cong g[s]$ ] . thus , we may assume that @xmath170 . in this case , if @xmath171 , then @xmath169\simeq h[s]-e\cong g[s]$ ] , since @xmath132 is then an isolating edge of @xmath169 $ ] . so , suppose that @xmath172 . if @xmath173 , we conclude that @xmath169\simeq h[s]-v\cong g[s\backslash \{v\}]$ ] , where the homotopy equivalence is due to the inclusion @xmath174}(x)\subseteq n_{h[s]}(v)$ ] ( see theorem  [ thm : hom - induction ] ) . it follows that we may further assume @xmath175 . we then define @xmath176 , and consider the mayer - vietoris sequence of the pair @xmath177,x)$ ] : @xmath178-n_{h[s^*]}[x])\to \widetilde{h}_{m-1}(h[s^*]-x)\to \widetilde{h}_{m-1}(h[s^ * ] ) \to \cdots.\ ] ] note that @xmath179)=0 $ ] by the maximality of @xmath20 . moreover , since @xmath180-x\cong h[s]$ ] , we need to have @xmath179-x)\neq 0 $ ] . therefore , we conclude that @xmath179-n_{h[s^*]}[x])\neq 0 $ ] . but , @xmath180-n_{h[s^*]}[x]\cong h[s\backslash \{u\}]$ ] and @xmath181\cong g[s\backslash \{u\}]$ ] so that we have @xmath182)\neq 0 $ ] . as a result , we deduce that @xmath183 . assume now that @xmath184 , and let @xmath31 be a maximal subset satisfying @xmath185)\neq 0 $ ] . similar to the previous cases , we may assume that @xmath186 and @xmath187 . suppose first that @xmath37 . then , @xmath188\simeq \sigma(g[w]-n_{g[w]}[u])$ ] , since @xmath0 has degree one in @xmath188 $ ] and @xmath50 is its only neighbor . it follows that @xmath189-n_{g[w]}[u])\neq 0 $ ] . we define @xmath190 . since @xmath132 is an isolating edge in @xmath191 $ ] , we have @xmath191\simeq h[k]-e$ ] . however , the vertex @xmath50 is of degree one in @xmath191-e$ ] and @xmath0 is its only neighbor ; hence , @xmath191-e\simeq \sigma((h[k]-e)-n_{h[k]-e}[x]))$ ] by theorem  [ thm : hom - induction ] . on the other hand , we have @xmath192-e)-n_{h[k]-e}[x]\cong g[w]-n_{g[w]}[u]$ ] so that @xmath193)\neq 0 $ ] . finally , suppose now that @xmath33 . as in the previous case , we let @xmath194 , and consider the mayer - vietoris sequence of the pair @xmath195,x)$ ] : @xmath196-n_{g[w^*]}[x])\to \widetilde{h}_{n-1}(g[w^*]-x)\to \widetilde{h}_{n-1}(g[w^ * ] ) \to \cdots.\ ] ] again , we have @xmath197)=0 $ ] by the maximality of @xmath198 . since @xmath199-x\cong g[w]$ ] , the group @xmath197-x)$ ] is nontrivial that implies @xmath197-n_{g[w^*]}[x])\neq 0 $ ] . however , @xmath199-n_{g[w^*]}[x]\cong g[w\backslash \{u\}]$ ] and @xmath200\cong h[w\backslash \{u\}]$ ] so that we have @xmath201)\neq 0 $ ] . as a result , we deduce that @xmath202 . this completes the proof . we next verify that the homotopy type of lozin s transform can be deduced from the source graph . [ lem : lozin+stable ] let @xmath8 be a graph and let @xmath9 be given . then @xmath203 for any two distinct decompositions @xmath204 and @xmath205 of @xmath136 . to prove the claim , it is enough to verify that for a given decomposition @xmath143 and a vertex @xmath206 , the complexes @xmath207 and @xmath208 have the same homotopy type . however , moving the vertex @xmath50 from @xmath138 to @xmath137 corresponds to the sequence of isolating operations @xmath209 and @xmath210 in @xmath144 ; therefore , the claim follows from theorem  [ thm : isolating ] . [ prop : lozin+stable ] let @xmath8 be a graph and let @xmath9 be given . then @xmath211 .    in view of lemma [ lem : lozin+stable ] , it is sufficient to show that @xmath212 . in such a case , we set @xmath213 and note that @xmath214 so that @xmath215 is homotopy equivalent to @xmath216 , while the latter graph is clearly isomorphic to @xmath217 , where @xmath218 is induced by the edge @xmath219 . it then follows that @xmath220 as required . [ lem : lozin+reg ] let @xmath8 be a graph and let @xmath9 be given . then @xmath221 for any two distinct decompositions @xmath204 and @xmath205 of @xmath136 . we proceed as in the proof of lemma  [ lem : lozin+stable ] . so , let a decomposition @xmath143 and a vertex @xmath206 be given . we claim that @xmath222 . if we set @xmath223 , then the edge @xmath224 is an isolating edge of @xmath94 with respect to the vertex @xmath225 , while @xmath225 has a neighbor @xmath226 of degree two . therefore , proposition  [ prop : reg+isolating ] applies , that is , @xmath227 . on the other hand , @xmath228 is also an isolating edge in @xmath94 with respect to @xmath226 , and the vertex @xmath226 has a degree two neighbor , namely @xmath225 . thus we have @xmath229 . so the claim follows . given a subset @xmath97 . assume first that @xmath175 . if we define @xmath230 , it follows that @xmath231\cong g[s]\cup k_2 $ ] , where @xmath218 is induced by the edge @xmath232 . therefore , the complex @xmath233)$ ] is homotopy equivalent to the suspension of @xmath234)$ ] . suppose now that @xmath173 . in such a case , we consider @xmath235 , and write @xmath236 $ ] and @xmath237 $ ] . note that the lozin s transform @xmath238 of @xmath94 with respect to the partition @xmath239 is exactly isomorphic to @xmath240 . therefore , we have @xmath241 by proposition  [ prop : lozin+stable ] , which implies that @xmath242 .    for the converse , by lemma  [ lem : lozin+reg ] , it is sufficient to show that @xmath243 . so , set @xmath244 . then we have @xmath245)+1\}.\ ] ] by corollary  [ cor : induction - sc ] . however , the graph @xmath246 is isomorphic to @xmath247 so that @xmath248 . moreover , the graph @xmath249 $ ] is isomorphic to @xmath250 in which @xmath142 is an isolated vertex . it means that @xmath251)={\textrm{reg}}(g - x)\leq { \textrm{reg}}(g)$ ] . therefore , we conclude that @xmath252 as claimed . a special case of lozin s transformation can be obtained by taking one of the sets in the partition of @xmath136 as a singleton . in other words , for a given @xmath253 , we consider the operation @xmath254 . observe that the resulting graph can be obtained from @xmath1 by replacing the edge @xmath255 in @xmath1 by a path @xmath256 , which is called the _ triple subdivision _ of @xmath1 with respect to the edge @xmath255 . following theorem  [ thm : lozin+reg ] , we may readily describe the effect of a triple subdivision on regularity . [ cor : lozin+edgesubdiv ] let @xmath1 be a graph and let @xmath53 be an edge . if @xmath257 is the graph obtained from @xmath1 by the triple subdivision of @xmath132 , then @xmath258 . in this section , we provide various upper bounds on the regularity of graphs as an application of theorem  [ thm : lozin+reg ] . we first recall that a @xmath259-(vertex ) coloring of a graph @xmath8 is a surjective mapping @xmath260 such that if @xmath261 , then @xmath262 , and the chromatic number @xmath263 of @xmath1 is the least integer @xmath264 for which @xmath1 admits a @xmath264-coloring . moreover , a graph @xmath1 is called _ perfect _ if @xmath265)=\omega(g[a])$ ] for any @xmath266 .    for a given graph @xmath1 with at least one edge , we define a graph @xmath267 , whose vertices are the edges of @xmath1 , that is , @xmath268 , and if @xmath132 and @xmath269 are two edges in @xmath1 , then @xmath270 if and only if @xmath271\cong 2k_2 $ ] . we remark that the graph @xmath267 constructed here is exactly the complement of that introduced in  @xcite . furthermore , the induced matching number of @xmath1 equals to the clique number of @xmath267 , i.e. , @xmath272 , and under suitable restrictions , we can say more :      assume that @xmath275 , and let @xmath276 $ ] be a proper vertex coloring of @xmath267 . we consider color classes @xmath277 and denote by @xmath278 , the subgraph of @xmath1 with @xmath279 for any @xmath280 $ ] . we then claim that each @xmath278 is a cochordal subgraph of @xmath1 . observe first that the graph @xmath278 can not contain @xmath281 for any @xmath282 , since @xmath1 is triangle - free . moreover , if @xmath278 contains @xmath283 , then @xmath1 must contain a chord that in turn creates a triangle in @xmath1 which is not possible . on the other hand , since the set of edges of @xmath278 corresponds to a color class in @xmath267 , it is necessarily @xmath284-free . therefore , the family @xmath285 is a cochordal edge cover of @xmath1 ; hence , @xmath286 . suppose now that @xmath287 , and let @xmath288 be a cochordal edge covering family of @xmath1 . we then define @xmath289 $ ] by @xmath290\colon e\in e(w_j)\}$ ] , and claim that @xmath291 is a proper coloring of @xmath267 . for this , if @xmath270 for some @xmath292 , there exists no @xmath293 $ ] for which @xmath294 , since @xmath295 is cochordal . we therefore have @xmath296 . this proves that @xmath297 .    by theorem  [ thm : chromatic - cochord ] , we note that the inequality @xmath298 holds for any graph @xmath1 containing at least one edge . furthermore , the followings are also immediate from theorem  [ thm : chromatic - cochord ] :          one of the important problem in graph coloring theory is to provide an upper bound on the chromatic number of a graph in terms of its clique number . under certain conditions on the source graphs , we next show that such a bound is possible for their associated graphs . for any given integer @xmath301 , we denote by @xmath302 , the class of graphs contained in @xmath303 . we proceed by an induction on the size of @xmath1 . we first note that if @xmath1 is a forest , then @xmath306 by proposition  [ prop : chordal - reg ] ; hence , @xmath307 by theorem  [ thm : chromatic - cochord ] . so , we may assume that @xmath1 contains at least one induced cycle , say @xmath308 , of order at least @xmath309 . _ proof of claim 1 . _ if the induced cycle @xmath308 contains at most one vertex of degree three , we can clearly construct such a path on @xmath308 . on the other hand , if @xmath311 are two vertices having degree three in @xmath1 , then all vertices ( except possibly @xmath0 and @xmath140 ) on the shortest path in @xmath308 connecting @xmath0 and @xmath140 must have degree two , since @xmath1 is @xmath312-free . moreover , the length of such a path is at least @xmath313 which proves the claim . we sometimes write @xmath330 for the graph obtained from @xmath1 by applying @xmath259 lozin s transformations on @xmath1 such that @xmath331 where @xmath332 . the following is an immediate consequence of corollary  [ cor : bound - m ] and theorem  [ thm : lozin+reg ] .      in the rest of this section , as an another application of theorem  [ thm : lozin+reg ] , we show that the regularity of a graph is always less than or equal to the sum of its induced matching and decycling numbers . to achieve this , we first verify that the whiskering of a graph with respect to a decycling set results a vertex decomposable graph which will be of independent interest . we recall that a vertex @xmath9 is called a _ leaf _ if it has only one neighbor in @xmath1 , and a _ pendant edge _ in @xmath1 is an edge which is incident to a leaf . the _ whisker _ @xmath334 of a graph @xmath8 with respect to a given subset @xmath335 is the graph constructed from @xmath1 by @xmath336 and @xmath337 . in particular , we abbreviate @xmath338 by @xmath339 ( see  @xcite ) .    for a graph @xmath1 and @xmath340 , if @xmath341 is acyclic , i.e. , contains no induced cycle , then @xmath342 is said to be a _ decycling set _ of @xmath1 . the size of a smallest decycling set of @xmath1 is called the _ decycling number _ of @xmath1 and denoted by @xmath343 ( see  @xcite ) . suppose @xmath346 is a minimum decycling set of @xmath257 , and let @xmath347 be the resulting path obtained after the triple subdivision of @xmath132 . note that @xmath348 , since @xmath20 is minimal . if @xmath349 , then @xmath20 is a decycling set for @xmath1 . so , assume that @xmath350 . in such a case , the vertices @xmath50 and @xmath51 can not both belong to @xmath20 , since otherwise the set @xmath351 would still be a decycling set for @xmath257 . therefore , we may assume @xmath167 without loss of generality . however , it then follows that @xmath352 is a decycling set for @xmath1 . thus , the inequality @xmath353 holds . consider @xmath173 , and let @xmath354 be the leaf neighbor of @xmath0 in @xmath334 . we note that the vertex @xmath0 is clearly a shedding vertex of @xmath334 and @xmath355)-\{u'\colon u\in n_g(x)\}=w_{s\backslash n_g[x]}(g - n_g[x]).\end{aligned}\ ] ] moreover , the sets @xmath356 and @xmath357 $ ] are decycling sets for graphs @xmath60 and @xmath115 $ ] respectively ; hence , both graphs @xmath358 and @xmath359}(g - n_g[x])$ ] are vertex decomposable by the induction on @xmath360 . it then follows that the graphs @xmath361 and @xmath362 $ ] are vertex decomposable , since the vertex @xmath354 is an isolated vertex of @xmath361 , and similarly , @xmath363 is a set of isolated vertices in @xmath362 $ ] . we let @xmath365 be a graph obtained from @xmath1 by a necessary number , say @xmath366 , of triple subdivisions on @xmath1 so that it is a @xmath118-free graph . we first recall that @xmath367 by proposition  [ prop : edge - sub - div - decy ] . assume that @xmath20 is a minimal decycling set for @xmath365 . by proposition  [ prop : whisker - vd ] , the graph @xmath368 is vertex decomposable . we therefore have @xmath369 by theorem  [ thm : vd - reg ] , since @xmath368 is also @xmath118-free . now , it follows that @xmath370 so that @xmath364 as required .    we remark that theorem  [ thm : reg - decycling ] is particularly useful when the graph has a small decycling number . having this in mind , we recall that a graph @xmath1 is called _ unicyclic _ provided that it has exactly one cycle . we follow the proof of theorem  [ thm : reg - decycling ] and write @xmath365 for the graph obtained from @xmath1 by @xmath259-triple subdivisions on @xmath1 so that @xmath365 is @xmath118-free . now , the set @xmath373 is a decycling set for @xmath365 so that @xmath374 is vertex decomposable by proposition  [ prop : whisker - vd ] . therefore , we have @xmath375 . however , the graph @xmath374 can be constructed from @xmath339 by @xmath259-triple subdivisions on the same edges of @xmath1 , that is , @xmath376 . thus , we have @xmath377 so that @xmath378 . on the other hand , the equality @xmath379 can be easily verified .
we prove that when a lozin s transformation is applied to a graph , the ( castelnuovo - mumford ) regularity of the graph increases exactly by one , as it happens to its induced matching number . as a consequence , we show that the regularity of a graph can be bounded from above by a function of its induced matching number . 
 we also prove that the regularity of a graph is always less than or equal to the sum of its induced matching and decycling numbers .