No Access

Maximal independent sets and regularity of graphs

Tran Nam Trung

Tran Nam Trung

Institute of Mathematics, Vast, 18 Hoang Quoc Viet, Hanoi, Vietnam

Timas, Thang Long University, Hanoi, Vietnam

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0218196721500375Cited by:0 (Source: Crossref)

Abstract

In this paper, we give a lower bound of the number of maximal independent sets in a graph $G$ in terms of the Castelnuovo–Mumford regularity of its edge ideal. We also find two classes of graphs achieving this minimum value.

Communicated by J. McCullough

Keywords:

AMSC: 05C30, 05D15

References

1. K. Cameron and T. Walker , The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49–55. Crossref, Web of Science, Google Scholar
2. G. J. Chang and M. J. Jou , The number of maximal independent sets in connected triangle-free graphs, Discrete Math. 197–198 (1999) 169–178. Crossref, Web of Science, Google Scholar
3. A. Constantinescu and M. Varbaro , Koszulness, Krull dimension, and other properties of graph related algebras, J. Algebraic Combin. 34 (2011) 375–400. Crossref, Web of Science, Google Scholar
4. H. Dao, C. Huneke and J. Schweig , Bounds on the regularity and projective dimension of ideals associated to graphs, J. Algebr. Comb. 38(1) (2013) 37–55. Crossref, Web of Science, Google Scholar
5. D. Eisenbud , Commutative Algebra: With a View Toward Algebraic Geometry (Springer-Verlag, New York, 1995). Crossref, Google Scholar
6. Z. Füredi , The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987) 463–470. Crossref, Web of Science, Google Scholar
7. J. R. Griggs, C. M. Grinstead and D. R. Guichard , The number of maximal independent sets in a connected graph, Discrete Math. 68 (1988) 211–220. Crossref, Web of Science, Google Scholar
8. H. T. Hà, Regularity of squarefree monomial ideals, in Connections Between Algebra, Combinatorics, and Geometry, eds. S. M. Cooper and S. Sather-Wagstaff, Springer Proceedings in Mathematics & Statistics, Vol. 76 (2014), pp. 251–276. Google Scholar
9. H. T. Hà and A. Van Tuyl , Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, J. Algebraic Combin. 27(2) (2008) 215–245. Crossref, Web of Science, Google Scholar
10. T. Hibi, A. Higashitani, K. Kimura and A. B. O’Keefe , Algebraic study on Cameron–Walker graphs, J. Algebra 422 (2015) 257–269. Crossref, Web of Science, Google Scholar
11. L. T. Hoa and N. V. Trung , On the Castelnuovo–Mumford regularity and the arithmetic degree of monomial ideals, Math. Z. 229(3) (1998) 519–537. Crossref, Web of Science, Google Scholar
12. D. T. Hoang and T. N. Trung , Coverings, matchings and the number of maximal independent sets of graphs, Australas. J. Combin. 73 (2019) 424–431. Web of Science, Google Scholar
13. M. Hujter and Z. Tuza , The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math. 6 (1993) 284–288. Crossref, Web of Science, Google Scholar
14. M. Katzman , Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A 113(3) (2006) 435–454. Crossref, Web of Science, Google Scholar
15. J. Liu , Maximal independent sets in bipartite graphs, J. Graph Theory 17 (1993) 495–507. Crossref, Web of Science, Google Scholar
16. J. W. Moon and L. Moser , On cliques in graphs, Israel J. Math. 3 (1965) 23–28. Crossref, Web of Science, Google Scholar
17. S. A. Seyed Fakhari and S. Yassemi , Improved bounds for the regularity of edge ideals of graphs, Collect. Math. 69(2) (2018) 249–262. Crossref, Web of Science, Google Scholar
18. T. N. Trung , Regularity, matchings and Cameron–Walker graphs, Collect. Math. 71(1) (2020) 83–91. Crossref, Web of Science, Google Scholar
19. A. Van Tuyl and R. H. Villarreal , Shellable graphs and sequentially Cohen Macaulay bipartite graphs, J. Combin. Theory Ser. A 115(5) (2008) 799–814. Crossref, Web of Science, Google Scholar
20. R. Villarreal , Monomial Algebras, Monographs and Textbooks in Pure and Applied Mathematics, Vol. 238 (Marcel Dekker, New York, 2001). Google Scholar
21. H. S. Wilf , The number of maximal independent sets in a tree, SIAM J. Algebraic Discrete Methods 7 (1986) 125–130. Crossref, Web of Science, Google Scholar
22. R. Woodroofe , Matchings, coverings, and Castelnuovo–Mumford regularity, J. Commut. Algebra 6 (2014) 287–304. Crossref, Web of Science, Google Scholar