Dominating induced matchings of finite graphs and regularity of edge ideals

详细信息    查看全文

• 作者：Takayuki Hibi ; Akihiro Higashitani ; Kyouko Kimura…
• 关键词：Edge ideal ; Dominating induced matching ; Regularity ; Unmixed graph ; Vertex decomposable graph
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：43
• 期：1
• 页码：173-198
• 全文大小：775 KB
• 参考文献：1.Biyikoğlu, T., Civan, Y.: Vertex decomposable graphs, codismantlability, Cohen–Macaulayness and Castelnuovo–Mumford regularity. Electron. J. Combin. 21 (2014)
  2.Biyikoğlu, T., Civan, Y.: Bounding Castelnuovo–Mumford Regularity of Graphs Via Lozin’s Transformation, preprint, arXiv:​1302.​3064v1
  3.Biyikoğlu, T., Civan, Y.: Castelnuovo–Mumford Regularity of Graphs, preprint, arXiv:​1503.​06018
  4.Cameron, K., Walker, T.: The graphs with maximum induced matching and maximum matching the same size. Discrete Math. 299, 49–55 (2005)MATH MathSciNet CrossRef
  5.Cardoso, D.M., Martins, E.A., Media, L., Rojo, O.: Spectral Results for the Dominating Induced Matching Problem, preprint, arXiv:​1311.​2748v1
  6.Dao, H., Huneke, C., Schweig, J.: Bounds on the regularity and projective dimension of ideals associated to graphs. J. Algebraic Combin. 38, 37–55 (2013)MATH MathSciNet CrossRef
  7.Francisco, C.A., Van Tuyl, A.: Sequentially Cohen–Macaulay edge ideals. Proc. Am. Math. Soc. 135, 2327–2337 (2007)MATH CrossRef
  8.Gitler, I., Valencia, C.E.: Bounds for invariants of edge-rings. Comm. Algebra 33, 1603–1616 (2005)MATH MathSciNet CrossRef
  9.Hà, H.T., Van Tuyl, A.: Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers. J. Algebraic Combin. 27, 215–245 (2008)MATH MathSciNet CrossRef
  10.Hibi, T., Higashitani, A., Kimura, K., O’Keefe, A.B.: Algebraic study on Cameron–Walker graphs. J. Algebra 422, 257–269 (2015)MATH MathSciNet CrossRef
  11.Kalai, G., Meshulam, R.: Intersections of Leray complexes and regularity of monomial ideals. J. Combin. Theory Ser. A 113, 1586–1592 (2006)MATH MathSciNet CrossRef
  12.Katzman, M.: Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory Ser. A. 113, 435–454 (2006)MATH MathSciNet CrossRef
  13.Khosh-Ahang, F., Moradi, S.: Regularity and projective dimension of edge ideal of \(C_5\) -free vertex decomposable graphs. Proc. Am. Math. Soc. 142, 1567–1576 (2014)MATH MathSciNet CrossRef
  14.Kimura, K.: Non-vanishingness of Betti numbers of edge ideals. In: Harmony of Gröbner Bases and the Modern Industrial Society, pp. 153–168. World Scientific, Singapore (2012)
  15.Kummini, M.: Regularity, depth and arithmetic rank of bipartite edge ideals. J. Algebraic Combin. 30, 429–445 (2009)MATH MathSciNet CrossRef
  16.Lin, M.C., Mizrahi, M.J., Szwarcfiter, J. L.: Exact Algorithms for Dominating Induced Matchings, preprint, arXiv:​1301.​7602v2
  17.Lyubeznik, G.: A new explicit finite free resolution of ideals generated by monomials in an \(R\) -sequence. J. Pure Appl. Algebra 51, 193–195 (1988)MATH MathSciNet CrossRef
  18.Mahmoudi, M., Mousivand, A., Crupi, M., Rinaldo, G., Terai, N., Yassemi, S.: Vertex decomposability and regularity of very well-covered graphs. J. Pure Appl. Algebra 215, 2473–2480 (2011)MATH MathSciNet CrossRef
  19.Nevo, E.: Regularity of edge ideals of \(C_4\) -free graphs via the topology of the lcm-lattice. J. Combin. Theory Ser. A 118, 491–501 (2011)MATH MathSciNet CrossRef
  20.Van Tuyl, A.: Sequentially Cohen–Macaulay bipartite graphs: vertex decomposability and regularity. Arch. Math. (Basel) 93, 451–459 (2009)MATH MathSciNet CrossRef
  21.Woodroofe, R.: Vertex decomposable graphs and obstructions to shellability. Proc. Am. Math. Soc. 137, 3235–3246 (2009)MATH MathSciNet CrossRef
  22.Woodroofe, R.: Matchings, coverings, and Castelnuovo–Mumford regularity. J. Commut. Algebra 6, 287–304 (2014)MATH MathSciNet CrossRef
  23.Zheng, X.: Resolutions of facet ideals. Comm. Algebra 32, 2301–2324 (2004)MATH MathSciNet CrossRef
  
• 作者单位：Takayuki Hibi (1)
  Akihiro Higashitani (2)
  Kyouko Kimura (3)
  Akiyoshi Tsuchiya (1)
  
  1. Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka, 560-0043, Japan
  2. Department of Mathematics, Kyoto Sangyo University, Motoyama, Kamigamo, Kita-ku, Kyoto, 603-8555, Japan
  3. Department of Mathematics, Faculty of Science, Shizuoka University, 836 Ohya, Suruga-ku, Shizuoka, 422-8529, Japan
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Order, Lattices and Ordered Algebraic Structures
  Computer Science, general
  Group Theory and Generalizations
  
• 出版者：Springer U.S.
• ISSN：1572-9192

文摘

The regularity of the edge ideal of a finite simple graph G is at least the induced matching number of G and is at most the minimum matching number of G. If G possesses a dominating induced matching, i.e. an induced matching which forms a maximal matching, then the induced matching number of G is equal to the minimum matching number of G. In the present paper, from viewpoints of both combinatorics and commutative algebra, finite simple graphs with dominating induced matchings will be mainly studied.