On the three graph invariants related to matching of finite simple graphs
DOI:
https://doi.org/10.13069/jacodesmath.v12i3.255Keywords:
Induced matching number, Minimum matching number, Matching number, Edge ideal, Castelnuovo–Mumford regularityAbstract
Let $G$ be a finite simple graph on the vertex set $V(G)$ and let $\text{ind-match}(G)$, $\text{min-match}(G)$ and $\text{match}(G)$ denote the induced matching number, the minimum matching number and the matching number of $G$, respectively. It is known that the inequalities $\text{ind-match}(G) \leq \text{min-match}(G) \leq \text{match}(G) \leq 2\text{min-match}(G)$ and $\text{match}(G) \leq \left\lfloor |V(G)|/2 \right\rfloor$ hold in general. In the present paper, we determine the possible tuples $(p, q, r, n)$ with $\text{ind-match}(G) = p$, $\text{min-match}(G) = q$, $\text{match}(G) = r$ and $|V(G)| = n$ arising from connected simple graphs. As an application of this result, we also determine the possible tuples $(p', q, r, n)$ with $\mathrm{reg}(G) = p'$, $\text{min-match}(G) = q$, $\text{match}(G) = r$ and $|V(G)| = n$ arising from connected simple graphs, where $I(G)$ is the edge ideal of $G$ and $\mathrm{reg}(G) = \mathrm{reg}(K[V(G)]/I(G))$ is the Castelnuovo--Mumford regularity of the quotient ring $K[V(G)]/I(G)$.
Accepted: 30 May 2023
Downloads
References
T. C. Adefokun, D. O. Ajayi, On maximum induced matching numbers of special grids, J. Math. Appl. 41 (2018) 5–18.
S. Arumugam, S. Velammal, Edge domination in graphs, Taiwanese J. Math. 2 (1998) 173–179.
R. Boliac, K. Cameron, V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241–253.
K. Cameron, T. Walker, The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49–55.
S. M. Cioabă, D. A. Gregory, W. H. Haemers, Matchings in regular graphs from eigenvalues, J. Combin. Theory Ser. B 99 (2009) 287–297.
M. Crupi, G. Rinaldo, N. Terai, Cohen–Macaulay edge ideal whose height is half of the number of vertices, Nagoya Math. J. 201 (2011) 117–131.
M. Crupi, G. Rinaldo, N. Terai, K. Yoshida, Effective Cowsik–Nori theorem for edge ideals, Comm. Algebra 38 (2010) 3347–3357.
H. Dao, C. Huneke, J. Schweig, Bounds on the regularity and projective dimension of ideals associated to graphs, J. Algebraic Combin. 38 (2013) 37–55.
R. Dutton, W. F. Klostermeyer, Edge dominating sets and vertex covers, Discuss. Math. Graph Theory 33 (2013) 437–456.
N. Erey, T. Hibi, The size of Betti tables of edge ideals arising from bipartite graphs, Proc. Amer. Math. Soc. 150 (2022) 5073–5083.
R. Fröberg, On Stanley–Reisner rings, Topics in algebra, Banach Center Publications 26 (1990) 57–70.
M. Fürst, D. Rautenbach, On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs, Theoret. Comput. Sci. 804 (2020) 126–138.
C. Godsil, G. Royle, Algebraic graph theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York (2001).
H. T. Hà, T. Hibi, MAX MIN vertex cover and the size of Betti tables, Ann. Comb. 25 (2021) 115–132.
H. T. Hà, A. Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, J. Algebraic Combin. 27 (2008) 215–245.
P. Hall, On representatives of subsets, J. Lond. Math. Soc. 10(1) (1935) 26–30.
T. Hibi, A. Higashitani, K. Kimura, A. B. O’Keefe, Algebraic study on Cameron–Walker graphs, J. Algebra 422 (2015) 257–269.
T. Hibi, A. Higashitani, K. Kimura, A. Tsuchiya, Dominating induced matchings of finite graphs and regularity of edge ideals, J. Algebraic Combin. 43 (2016) 173–198.
T. Hibi, H. Kanno, K. Kimura, K. Matsuda, A. Van Tuyl, Homological invariants of Cameron–Walker graphs, Trans. Amer. Math. Soc. 374(9) (2021) 6559–6582.
T. Hibi, H. Kanno, K. Matsuda, Induced matching numbers of finite graphs and edge ideals, J. Algebra 532 (2019) 311–322.
T. Hibi, K. Kimura, K. Matsuda, A. Tsuchiya, Regularity and a-invariant of Cameron–Walker graphs, J. Algebra 584 (2021) 215–242.
T. Hibi, K. Kimura, K. Matsuda, A. Van Tuyl, The regularity and h-polynomial of Cameron–Walker graphs, Enumer. Combin. Appl. 2(2) (2022).
T. Hibi, K. Matsuda, A. Van Tuyl, Regularity and h-polynomials of edge ideals, Electron. J. Combin. 26 (2019).
A. Hirano, K. Matsuda, Matching numbers and dimension of edge ideals, Graphs Combin. 37 (2021) 761–774.
M. Katzman, Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A 113 (2006) 435–454.
F. Khosh-Ahang, S. Moradi, Regularity and projective dimension of the edge ideal of C5-free vertex decomposable graphs, Proc. Amer. Math. Soc. 142(5) (2014) 1567–1576.
M. Las Vergnas, A note on matchings in graphs, Colloque sur la Théorie des Graphes (Paris 1974), Cahiers Centre Études Rech. Opér. 17 (1975) 257–260.
S. Morey, R. H. Villarreal, Edge ideals: algebraic and combinatorial properties, in: Progress in commutative algebra 1, de Gruyter, Berlin (2012) 85–126.
E. Nevo, I. Peeva, C4-free edge ideals, J. Algebraic Combin. 37 (2013) 243–248.
I. Peeva, Graded syzygies, Algebra and Applications 14, Springer, London (2011).
F. Romeo, Chordal circulant graphs and induced matching number, Discrete Math. 343 (2020) 111947.
S. A. Seyed Fakhari, Regularity of symbolic powers of edge ideals of Cameron–Walker graphs, Comm. Algebra 48 (2020) 5215–5223.
A. Simis, W. V. Vasconcelos, R. H. Villarreal, On the ideal theory of graphs, J. Algebra 167 (1994) 389–416.
W. Song, L. Miao, H. Wang, Y. Zhao, Maximal matching and edge domination in complete multipartite graphs, Int. J. Comput. Math. 91 (2014) 857–862.
D. P. Sumner, Graphs with 1-factors, Proc. Amer. Math. Soc. 42 (1974) 8–12.
T. N. Trung, Regularity, matchings and Cameron–Walker graphs, Collect. Math. 71 (2020) 83–91.
R. H. Villarreal, Monomial algebras, Monographs and Textbooks in Pure and Applied Mathematics 238, Marcel Dekker, Inc., New York (2001).
R. Woodroofe, Matchings, coverings, and Castelnuovo–Mumford regularity, J. Commut. Algebra 6 (2014) 287–304.
