Scholarlink

<p>Let <i>G</i> be a graph. The Laplacian ratio of <i>G</i> is the permanent of the Laplacian matrix of <i>G</i> divided by the product of degrees of all vertices. The computational complexity of Laplacian ratio is #P-complete. Brualdi and Goldwasser studied systematically the properties of Laplacian ratios of graphs. And they proposed an open problem: what is the minimum value of the Laplacian ratios of trees with <i>n</i> vertices having diameter at least <i>k</i>? In this paper, we give a solution to the problem.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Solution to an Open Problem on Laplacian Ratio

  • 期刊论文

  • 发表日期：

    2025年6月10日

查看全文
  • Tingzeng Wu,
  • Xiangshuai Dong,
  • Hongjian Lai,
  • Xiaolin Zeng

摘要

Let G be a graph. The Laplacian ratio of G is the permanent of the Laplacian matrix of G divided by the product of degrees of all vertices. The computational complexity of Laplacian ratio is #P-complete. Brualdi and Goldwasser studied systematically the properties of Laplacian ratios of graphs. And they proposed an open problem: what is the minimum value of the Laplacian ratios of trees with n vertices having diameter at least k? In this paper, we give a solution to the problem.