Geodesic
Some Results on the Independence Polynomial of Unicyclic Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 515-524

Voir la notice de l'article provenant de la source Library of Science

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).
Keywords: independence polynomial, independent set, unicyclic graphs 
Oboudi, Mohammad Reza. Some Results on the Independence Polynomial of Unicyclic Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 515-524. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a13/
@article{DMGT_2018_38_2_a13,
     author = {Oboudi, Mohammad Reza},
     title = {Some {Results} on the {Independence} {Polynomial} of {Unicyclic} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {515--524},
     year = {2018},
     volume = {38},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a13/}
}
TY  - JOUR
AU  - Oboudi, Mohammad Reza
TI  - Some Results on the Independence Polynomial of Unicyclic Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 515
EP  - 524
VL  - 38
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a13/
LA  - en
ID  - DMGT_2018_38_2_a13
ER  - 
%0 Journal Article
%A Oboudi, Mohammad Reza
%T Some Results on the Independence Polynomial of Unicyclic Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 515-524
%V 38
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a13/
%G en
%F DMGT_2018_38_2_a13

[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