solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6740次
Independence Equivalence Classes of Paths and Cycles. (arXiv:1810.05317v1 [math.CO])
来源于:arXiv
The independence polynomial of a graph is the generating polynomial for the
number of independent sets of each size. Two graphs are said to be
\textit{independence equivalent} if they have equivalent independence
polynomials. We extend previous work by showing that independence equivalence
class of every odd path has size 1, while the class can contain arbitrarily
many graphs for even paths. We also prove that the independence equivalence
class of every even cycle consists of two graphs when $n\ge 2$ except the
independence equivalence class of $C_6$ which consists of three graphs. The odd
case remains open, although, using irreducibility results from algebra, we were
able show that for a prime $p \geq 5$ and $n\ge 1$ the independence equivalence
class of $C_{p^n}$ consists of only two graphs. 查看全文>>