Independence Polynomials of Bipartite Graphs
Independence Polynomials of Bipartite Graphs
复制标题
二部图的独立多项式
DOI：
10.1007/s40840-022-01326-9
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Xia Hong
中科院分区：
文献类型：
--
作者：
Huihui Zhang;Xia Hong
给定一个具有顶点集的连通图G，若G的子集I中任意两个顶点之间没有边，则称G的子集I是独立的。设为基数为kofG的独立集的个数，令。G的独立多项式定义为，其中称为G的Merrifield-Simmons指数。本文考虑了二部图独立多项式系数的一些极值问题。首先确定了所有二部图中的第二大二部图，并刻画了所有二部图中同时最小化I（G;x）的所有系数的图。其次，在所有至少有一个圈的二部图中，确定最大的一个，并在所有具有给定匹配数的二部图中，确定使I（G;x）的所有系数最小的唯一图。直径最多为4，连通性）也被表征。
Given a connected graphGwith vertex set, a subsetIofis called independent if there are no edges between any two vertices fromI. Letbe the number of independent sets with cardinalitykofGand let. The independence polynomial ofGis defined as, whereis called the Merrifield–Simmons index ofG. In this paper, some extremal problems on the coefficients of the independence polynomial of bipartite graphs are considered. Firstly, the second largestamong all bipartite graphs is determined, and the graph which simultaneously minimizes all coefficients ofI(G;x) among all bipartite graphs is characterized. Secondly, the largestamong all bipartite graphs with at least one cycle is determined, and the unique graph which minimizes all coefficients ofI(G;x) among all bipartite graphs with given matching number (resp. diameter at most four, connectivity) is characterized as well.
登录
查看更多内容
DOI：
10.37236/7280
发表时间：
2018-02
期刊：
Electron. J. Comb.
影响因子：
--
作者：
Jason I. Brown;B. Cameron
通讯作者：
Jason I. Brown;B. Cameron
DOI：
10.1017/cbo9780511734885.004
发表时间：
2005
期刊：
--
影响因子：
--
作者：
P. Östergård
通讯作者：
P. Östergård
DOI：
10.1007/bf00551410
发表时间：
1980-01-01
期刊：
THEORETICA CHIMICA ACTA
影响因子：
--
作者：
MERRIFIELD, RE;SIMMONS, HE
通讯作者：
SIMMONS, HE
DOI：
10.1016/j.jcta.2016.06.019
发表时间：
2014-12
期刊：
J. Comb. Theory A
影响因子：
--
作者：
Jonathan Cutler;Luke Pebody
通讯作者：
Jonathan Cutler;Luke Pebody
DOI：
--
发表时间：
2013
期刊：
Ars Comb.
影响因子：
--
作者：
A. Frendrup;A. S. Pedersen;A. A. Sapozhenko-A.;P. Vestergaard
通讯作者：
A. Frendrup;A. S. Pedersen;A. A. Sapozhenko-A.;P. Vestergaard