On the coefficients of the independence polynomial of graphs

Shuchao Li (), Lin Liu () and Yueyu Wu ()
Additional contact information
Shuchao Li: Central China Normal University
Lin Liu: Central China Normal University
Yueyu Wu: Central China Normal University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 4, No 9, 1324-1342

Abstract: Abstract An independent set of a graph G is a set of pairwise non-adjacent vertices. Let $$i_k = i_k(G)$$ i k = i k ( G ) be the number of independent sets of cardinality k of G. The independence polynomial $$I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k$$ I ( G , x ) = ∑ k ⩾ 0 i k ( G ) x k defined first by Gutman and Harary has been the focus of considerable research recently, whereas $$i(G)=I(G, 1)$$ i ( G ) = I ( G , 1 ) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n, the kth coefficient $$i_k$$ i k is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number $$\omega $$ ω ) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number $$\chi $$ χ (resp. vertex connectivity $$\kappa $$ κ ) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.

Keywords: Independent set; Diameter; Girth; Chromatic number; Clique number; Connectivity; 05C35; 05C69; 05C15; 05C40 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0037-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:4:d:10.1007_s10878-016-0037-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0037-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().