Ir al contenido

Documat

Connected domination in graphs and v-numbers of binomial edge ideals

  • Jaramillo-Velez, Delio [1] ; Seccia, Lisa [2]
    1. [1] Centro de Investigación y de Estudios Avanzados

      Centro de Investigación y de Estudios Avanzados

      México

    2. [2] Max Planck Institute for Mathematics in the Sciences

      Max Planck Institute for Mathematics in the Sciences

      Kreisfreie Stadt Leipzig, Alemania

  • Localización: Collectanea mathematica, ISSN 0010-0757, Vol. 75, Fasc. 3, 2024, págs. 771-793
  • Idioma: inglés
  • DOI: 10.1007/s13348-023-00412-w
  • Enlaces
  • Resumen

    • The v-number of a graded ideal is an algebraic invariant introduced by Cooper et al., and originally motivated by problems in algebraic coding theory. In this paper we study the case of binomial edge ideals and we establish a significant connection between their v-numbers and the concept of connected domination in graphs. More specifically, we prove that the localization of the v-number at one of the minimal primes of the binomial edge ideal J_G of a graph G coincides with the connected domination number of the defining graph, providing a first algebraic description of the connected domination number. As an immediate corollary, we obtain a sharp combinatorial upper bound for the v-number of binomial edge ideals of graphs. Lastly, building on some known results on edge ideals, we analyse how the v-number of J_G behaves under Gröbner degeneration when G is a closed graph.

  • Referencias bibliográficas
    • Ambhore, S.B., Saha K., Sengupta, I.: The v-number of binomial edge ideals. arXiv:2304.06416 (2023)
    • Bo, C., Liu, B.: Some inequalities about connected domination number. Discrete Math. 159(1), 241–245 (1996)
    • Civan, Y.: The -number and Castelnuovo–Mumford regularity of graphs. J. Algebraic Combin. 57(1), 161–169 (2023)
    • Cooper, S.M., Seceleanu, A., Tohăneanu, ŞO., Pinto, M.V., Villarreal, R.H.: Generalized minimum distance functions and algebraic invariants...
    • Caro, Y., West, D.B., Yuster, R.: Connected domination and spanning trees with many leaves. SIAM J. Discrete Math. 13(2), 202–211 (2000)
    • Desormeaux, W.J., Haynes, T.W., Henning, M.A.: Bounds on the connected domination number of a graph. Discrete Appl. Math. 161(18), 2925–2931...
    • Eisenbud, D.: Commutative Algebra, Volume 50 of Graduate Texts in Mathematics. Springer, New York (1995). (With a view toward algebraic geometry)
    • Eisenbud, D.: The Geometry of Syzygies, Volume 229 of Graduate Texts in Mathematics. Springer, New York (2005). (A second course in commutative...
    • Ene, V., Zarojanu, A.: On the regularity of binomial edge ideals. Math. Nachr. 288(1), 19–24 (2015)
    • Francisco, C.A., Hà, H.T., Van Tuyl, A.: Associated primes of monomial ideals and odd holes in graphs. J. Algebraic Combin. 32(2), 287–301...
    • Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)
    • Geramita, A.V., Kreuzer, M., Robbiano, L.: Cayley–Bacharach schemes and their canonical modules. Trans. Am. Math. Soc. 339(1), 163–189 (1993)
    • Grisalde, G., Reyes, E., Villarreal, R.H.: Induced matchings and the v-number of graded ideals. Mathematics 9(22), 2860 (2021)
    • Grayson, D.R., Stillman, M.E.: Macaulay2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/
    • Harary, F.: Graph Theory. Addison-Wesley Publishing Co., Reading (1969)
    • Herzog, J., Hibi, T., Hreinsdóttir, F., Kahle, T., Rauh, J.: Binomial edge ideals and conditional independence statements. Adv. Appl. Math....
    • Herzog, J., Hibi, T., Ohsugi, H.: Binomial Ideals. Graduate Texts in Mathematics, vol. 279. Springer, Cham (2018)
    • Johnson, D.S., Garey, M.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
    • Jayanthan, A.V., Narayanan, N., Raghavendra Rao, B.V.: Regularity of binomial edge ideals of certain block graphs. Proc. Math. Sci. 129(3),...
    • Jaramillo, D., Villarreal, R.H.: The v-number of edge ideals. J. Combin. Theory Ser. A 177, 35 (2021)
    • Kiani, D., Madani, S.S.: The Castelnuovo–Mumford regularity of binomial edge ideals. J. Combin. Theory Ser. A 139, 80–86 (2016)
    • Karami, H., Sheikholeslami, S.M., Khodkar, A., West, D.B.: Connected domination number of a graph and its complement. Graphs Combin 28(1),...
    • Kosari, S., Shao, Z., Sheikholeslami, S.M., Chellali, M., Khoeilar, R., Karami, H.: A proof of a conjecture on the connected domination number....
    • Li, Y., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks....
    • Matsumura, H.: Commutative Ring Theory. Volume 8 of Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press, Cambridge...
    • Matsuda, K., Murai, S.: Regularity bounds for binomial edge ideals. J. Commut. Algebra 5(1), 141–149 (2013)
    • Mafuta, P., Mukwembi, S., Munyira, S.: Radius, leaf number, connected domination number and minimum degree. Quaestiones Mathematicae, 1–8...
    • Mohammadi, F., Sharifan, L.: Hilbert function of binomial edge ideals. Commun. Algebra 42(2), 688–703 (2014)
    • Núñez Betancourt, L., Pitones, Y., Villarreal, R.H.: Footprint and minimum distance functions. Commun. Korean Math. Soc. 33(1), 85–101 (2018)
    • Núñez Betancourt, L., Pitones, Y., Villarreal, R.H.: Bounds for the minimum distance function. An. Ştiinţ. Univ. “Ovidius’’ Constanţa Ser....
    • Ohtani, M.: Graphs and ideals generated by some 2-minors. Commun. Algebra 39(3), 905–917 (2011)
    • Ohtani, M.: Binomial edge ideals of complete multipartite graphs. Commun. Algebra 41(10), 3858–3867 (2013)
    • Pfaff, J., Laskar, R., Hedetniemi, S.T.: NP-completeness of total and connected domination, and irredundance for bipartite graphs. Technical...
    • Rouzbahani Malayeri, M., Madani, S.S., Kiani, D.: A proof for a conjecture on the regularity of binomial edge ideals. J. Combin. Theory Ser....
    • Seyed Fakhari, S.A., Shibata, K., Terai, N., Yassemi, S.: Cohen–Macaulay edge-weighted edge ideals of very well-covered graphs. Commun. Algebra...
    • Saeedi Madani, S., Kiani, D.: Binomial edge ideals of regularity 3. J. Algebra 515, 157–172 (2018)
    • Saha, K., Sengupta, I.: The -number of monomial ideals. J. Algebraic Combin. 56(3), 903–927 (2022)
    • Simis, A., Vasconcelos, W.V., Villarreal, R.H.: On the ideal theory of graphs. J. Algebra 167(2), 389–416 (1994)
    • Sampathkumar, E., Walikar, H.B.: The connected domination number of a graph. J. Math. Phys. Sci. 13, 607–613 (1979)
    • Schenzel, P., Zafar, S.: Algebraic properties of the binomial edge ideal of a complete bipartite graph. An. Ştiinţ. Univ. “Ovidius’’ Constanţa...
    • Villarreal, R.H.: Cohen–Macaulay graphs. Manuscr. Math. 66(3), 277–293 (1990)
    • Villarreal, R.H.: Monomial Algebras. Monographs and Research Notes in Mathematics, 2nd edn. CRC Press, Boca Raton, FL (2015)
    • Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw. Appl....
    • Wang, H., Zhu, G., Li, X., Zhang, J.: Algebraic properties of edge ideals of some vertex-weighted oriented cyclic graphs. Algebra Colloq....
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno