PROOF OF A CONJECTURE OF
PROOF OF A CONJECTURE OF
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
V. Nikiforov
中科院分区：
文献类型：
--
作者：
V. Nikiforov
这个值（连同图是否是二部图的信息）描述了给定长度的闭游动的数量的渐近行为，因为这个长度趋于无穷大，并且与G上随机游动的混合性质有关。很容易看出，如果考虑一个简单图G和它的补图G，那么μ G + μ G是一个范数为n−1的矩阵，所以μ（G）+μ（G）≥ n−1对G的所有选择都成立（这个不等式是尖锐的，例如对G是空图）。在她的论文中，Nosal [5]表明，如果G和G是补数，则μ（G）+ μ（G）≤ √ 2n-1。与平凡下界不同，这个值不是最优的：Nikiforov [4]将其改进为μ（G）+ μ（G）≤（μ 2 − 10−7）n
This value (together with the information of whether the graph is bipartite or not) describes the asymptotic behaviour of the number of closed walks of a given length as this length tends to infinity and is related to the mixing properties of the random walk on G. It is easy to see that if one considers a simple graph G and its complement G, then AdjG +AdjG is a matrix with norm n−1, so μ(G)+μ(G) ≥ n−1 holds for all choices of G (and this inequality is sharp e.g. for G the empty graph). In her thesis, Nosal [5] shows that if G and G are complements, then μ(G) + μ(G) ≤ √ 2n − 1. Unlike the trivial lower bound, this value is not optimal: Nikiforov [4] improved it to μ(G) + μ(G) ≤ ( √ 2 − 10−7)n