On the values of independence and domination polynomials at specific points

Document Type : Research Paper


1 Yazd University

2 Islamic Azad University


Let $G$ be a simple graph of order $n$‎. ‎We consider the‎ ‎independence polynomial and the domination polynomial of a graph‎ ‎$G$‎. ‎The value of a graph polynomial at a specific point can give‎ ‎sometimes a very surprising information about the structure of the‎ ‎graph‎. ‎In this paper we investigate independence and domination‎ ‎polynomial at $-1$ and $1$‎.


Main Subjects

S. Akbari, S. Alikhani, and Y. H. Peng (2010). Characterization of graphs using domination polynomial. European J. Combin.. 31, 1714-1724 S. Akbari and M. R. Oboudi Cycles are determined by their domination polynomials, to appear. Ars Combin.. Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erd\"os (1987). The vertex independence sequence of a graph is not constrained. Congr. Numer.. 58, 15-23 S. Alikhani and Y. H. Peng Introduction to domination polynomial of a graph, in press. Available at \texttt{http://arxiv.org/abs/0905.2251}.. Ars Combin.. S. Alikhani and Y. H. Peng (2011). Domination polynomials of cubic graphs of order 10. Turkish J. Math.. 35, 355-366 S. Alikhani and Y. H. Peng (2009). Dominating sets and domination polynomial of paths, 10 pages. Int. J. Math. Math. Sci.. S. Alikhani and Y. H. Peng (2010). Dominating sets and domination polynomials of certain graphs, II. Opuscula Math.. 30 (1), 37-51 S. Alikhani and Y. H. Peng (2011). Independence roots and independence fractals of certain graphs. J. Appl. Math. Comput.. 36, 89-100 P. N. Balister, B. Bollobas, J. Cutler, and L. Pebody (2002). The interlace polynomial of graphs at $-1$. European J. Combin.. 23, 761-767 A. E. Brouwer The number of dominating sets of a finite graph is odd. preprint. J. I. Brown, K. Dilcher and R. J. Nowakowski (2000). Roots of independence polynomials of well covered graphs. J. Algebraic Combin.. 11, 197-210 R. Frucht and F. Harary (1970). On the corona of two graphs. On the corona of two graphs. 4, 322-325 I. Gutman and F. Harary (1983). Generalizations of the matching polynomial. Utilitas Math.. 24, 97-106 R. P. Stanley (1973). Acyclic orientations of graphs. Discrete Math.. 5, 171-178