Some Results on the Independence Polynomial of Unicyclic Graphs

Oboudi, Mohammad Reza

Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 515-524.

Résumé

Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)= Σ_k=0^n s(G,k)x^k, where s(G, k) is the number of independent sets of G with size k and s(G, 0) = 1. A unicyclic graph is a graph containing exactly one cycle. Let C_n be the cycle on n vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs G on n vertices (except two of them), I(G, t) gt; I(C_n, t) for sufficiently large t. Finally for every n ≥ 3 we find all connected graphs H such that I(H, x) = I(C_n, x).

Détail

Keywords: independence polynomial, independent set, unicyclic graphs

Bibliographie

[1] S. Akbari, S. Alikhani, M.R. Oboudi and Y.H. Peng, On the zeros of domination polynomial of a graph, Combin. Graphs 531 (2010) 109–115. doi:10.1090/conm/531/10460

[2] S. Akbari and M.R. Oboudi, Cycles are determined by their domination polynomials, Ars Combin. 116 (2014) 353–358.

[3] S. Akbari and M.R. Oboudi, On the edge cover polynomial of a graph, European J. Combin. 34 (2013) 297–321. doi:10.1016/j.ejc.2012.05.005

[4] S. Akbari, M.R. Oboudi and S. Qajar, On the rational independence roots, Combin. Graphs 531 (2010) 149–157. doi:10.1090/conm/531/10464

[5] J.I. Brown, C.A. Hickman and R.J. Nowakowski, On the location of roots of independence polynomials, J. Algebraic Combin. 19 (2004) 273–282. doi:10.1023/B:JACO.0000030703.39946.70

[6] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a claw free graph, J. Combin. Theory Ser. B 97 (2007) 350–357. doi:10.1016/j.jctb.2006.06.001

[7] P. Csikvári and M.R. Oboudi, On the roots of edge cover polynomials of graphs, European J. Combin. 32 (2011) 1407–1416. doi:10.1016/j.ejc.2011.06.009

[8] T. Derikvand and M.R. Oboudi, On the number of maximum independent sets of graphs, Trans. Combin. 3 (2014) 29–36.

[9] I. Gutman, Some analytical properties of the independence and matching polynomials, MATCH Commun. Math. Comput. Chem. 28 (1992) 139–150.

[10] I. Gutman and F. Harary, Generalizations of the matching polynomial, Util. Math. 24 (1983) 97–106.

[11] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219–228. doi:10.1016/0012-365X(94)90163-5

[12] T. Kotek, J. Preen and P. Tittmann, Domination polynomials of graph products . arXiv:1305.1475v2.

[13] V.E. Levit and E. Mandrescu, The independence polynomial of a graph—A survey, Proceedings of the 1st International Conference on Algebraic Informatics (Aristotle Univ. Thessaloniki, Thessaloniki, 2005) 233–254.

[14] J.A. Makowsky, E.V. Ravve and N.K. Blanchard, On the location of roots of graph polynomials, European J. Combin. 41 (2014) 1–19. doi:10.1016/j.ejc.2014.03.003

[15] M.R. Oboudi, On the largest real root of independence polynomials of trees, Ars Combin., to appear.

[16] M.R. Oboudi, On the roots of domination polynomial of graphs, Discrete Appl. Math. 205 (2016) 126–131. doi:10.1016/j.dam.2015.12.010