论文标题
在独立性多项式的最大真实根上
On the largest real root of the independence polynomial of a unicyclic graph
论文作者
论文摘要
图$ g $的独立性多项式，表示为$ i（g，x）$，是针对每个大小的独立集数量的生成多项式。 $ i（g，x）$的根称为$ g $的\ textit {独立根}。众所周知，对于每个图$ g $，最小模量的独立根，表示为$ξ（g）$，都是真实的。所有图表上的关系$ \ prepeq $定义如下，$ h \ preceq g $ i时，仅当$ i（h，x）\ ge i（g，x）\ text {for All} x \ in [ξ（g），0]，0]。$。 我们发现，相对于$ \ preceq $，找到给定订单的最大和最小连接的独并覆盖的独环图。这扩展了Csikvári的2013年工作，其中确定了给定订单的最大树木和最小树，还回答了同一工作中提出的一个空旷的问题。我们的结果的推论给出了所有连接的（覆盖良好的）独一图表中最小化和最大化$ξ（g）$的图形。我们还回答了奥布迪（Oboudi）在2018年提出的更多相关的公开问题，并反驳了从2008年起列维特（Levit）和曼德雷斯库（Mandrescu）引起的猜想。
The independence polynomial of a graph $G$, denoted $I(G,x)$, is the generating polynomial for the number of independent sets of each size. The roots of $I(G,x)$ are called the \textit{independence roots} of $G$. It is known that for every graph $G$, the independence root of smallest modulus, denoted $ξ(G)$, is real. The relation $\preceq$ on the set of all graphs is defined as follows, $H\preceq G$ if and only if $I(H,x)\ge I(G,x)\text{ for all }x\in [ξ(G),0].$ We find the maximum and minimum connected unicyclic and connected well-covered unicyclic graphs of a given order with respect to $\preceq$. This extends 2013 work by Csikvári where the maximum and minimum trees of a given order were determined and also answers an open question posed in the same work. Corollaries of our results give the graphs that minimize and maximize $ξ(G)$ among all connected (well-covered) unicyclic graphs. We also answer more related open questions posed by Oboudi in 2018 and disprove a conjecture due to Levit and Mandrescu from 2008.
