On the unimodality of independence polynomial of certain classes of graphs

Document Type: Research Paper

Authors

1 Yazd University

2 Yazd university

Abstract

The independence polynomial of a graph $G$ is the polynomial‎ ‎$\sum i_kx^k$‎, ‎where $i_k$ denote the number of independent sets‎ ‎of cardinality $k$ in $G$‎. ‎In this paper we study unimodality‎ ‎problem for the independence polynomial of certain classes of‎ ‎graphs‎.

Keywords

Main Subjects


S. Alikhani (2009). Dominating sets and domination polynomials of graphs. Ph. D. Thesis, Universiti Putra Malaysia.
S. Alikhani and Y. H. Peng Introduction to domination polynomial of a graph. Ars Combin., in press, {http://arxiv.org/abs/0905.2251}..
S. Alikhani and F. Jafari (2012). On the independent sets of some nano-structures. Optoelectronics and advanced materials-rapid communications. 6 (9-10), 911-913
Y. Bai, B. Zhao and P. Zhao (2009). Extremal Merrifield-Simmons index and Hosoya index of polyphenyl chains. MATCH Commun. Math. Comput. Chem.. 62, 649-656
S. Barnard and J. F. Child (1955). Higher Algebra. Macmillan, London.
F. Brenti (1994). Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update. Contemp. Math.. 178, 417-441
R. A. Brualdi (1992). ntroductory combinatorics. Second edition. North-Holland Publishing Co., New York.
T. Dov{s}li'{c} and F. M.{a}lo{}y (2010). Chain hexagonal cacti: Matchings and independent sets. Discrete Math.. 310 (12), 1676-1690
C. Hoede and X. Li (1994). Clique polynomials and independent set polynomials of graphs. Discrete Math.. 25, 219-228
V. E. Levit and E. Mandrescu (2002). On well-covered trees with unimodal independence polynomials. Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002)., Congr. Numer.. 159, 193-202
V. E. Levit and E. Mandrescu (2004). Graph products with log-concave independence polynomials. WSEAS Trans. Math.. 3, 487-492
V. E. Levit and E. Mandrescu (2004). Very well-covered graphs with log-concave independence polynomials. Carpathian J. Math.. 20, 73-80
V. E. Levit and E. Mandrescu (2005). The independence polynomial of a graph—a survey. in: Proceedings of the 1st International Conference on Algebraic Informatics, Aristotle Univ. Thessaloniki, Thessaloniki. , 233-254
V. E. Levit and E. Mandrescu (2006). Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture. European J. Combin.. 27, 931-939
V. E. Levit and E. Mandrescu (2006). Partial unimodality for independence polynomials of K"{o}nig-Egerváry graphs. Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer.. 179, 109-119
V. E. Levit and E. Mandrescu (2007). A family of graphs whose independence polynomials are both palindromic and unimodal. Carpathian J. Math.. 23, 108-116
R. C. Read (1968). An introduction to chromatic polynomials. J. Combinatorial Theory. 4, 52-71
R. P. Stanley (1989). Log-concave and unimodal sequences in algebra, combinatorics and geometry. Ann. New York Acad. Sci.. 576, 500-535
Y. Wang and B. X. Zhu (2011). On the unimodality of independence polynomials of some graphs. European J. Combin.. 32, 10-20