Scholarlink

Abstract <p> Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> be a simple graph on <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n\)</EquationSource> </InlineEquation> vertices with weights <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\pm 1\)</EquationSource> </InlineEquation> on edges. Assume that for each edge <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(e\)</EquationSource> </InlineEquation>, the sum of the weights of the edges adjacent to <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(e\)</EquationSource> </InlineEquation> (including <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(e\)</EquationSource> </InlineEquation> itself) is positive. Let <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(g(n)\)</EquationSource> </InlineEquation> be the minimal possible sum of edge weights in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation>. It is known that <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(g(n)=(\kappa+o(1)) n^2\)</EquationSource> </InlineEquation>. We sharpen the lower bound of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\kappa\)</EquationSource> </InlineEquation> from <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(-1/25\)</EquationSource> </InlineEquation> to <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(-1/36\)</EquationSource> </InlineEquation>. </p>

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

On the Minimal Sum of Edge Weights in a Signed Edge-Dominated Graph: II

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • P. K. Prozorov,
  • D. D. Cherkashin

摘要

Abstract

Let \(G\) be a simple graph on \(n\) vertices with weights \(\pm 1\) on edges. Assume that for each edge \(e\) , the sum of the weights of the edges adjacent to \(e\) (including \(e\) itself) is positive. Let \(g(n)\) be the minimal possible sum of edge weights in \(G\) . It is known that \(g(n)=(\kappa+o(1)) n^2\) . We sharpen the lower bound of \(\kappa\) from \(-1/25\) to \(-1/36\) .