Scholarlink

<p>In this paper we show that prime sum graphs on <i>n</i> vertices – which are graphs on vertex set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\{1,2, \dots ,n\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> where <i>ij</i> is an edge when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(i+j\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>+</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation> is prime – contain all trees with at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\exp ( c \log n / \log \log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>exp</mo> <mo stretchy="false">(</mo> <mi>c</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.</p>

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

Prime Sum Graphs and the Induced Trees They Contain

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月21日

查看全文
  • Ernie Croot,
  • Patrick Jin

摘要

In this paper we show that prime sum graphs on n vertices – which are graphs on vertex set \(\{1,2, \dots ,n\}\) { 1 , 2 , ⋯ , n } where ij is an edge when \(i+j\) i + j is prime – contain all trees with at most \(\exp ( c \log n / \log \log n)\) exp ( c log n / log log n ) vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.