Scholarlink

<p>The <i>d-independence number</i> of a graph <i>G</i> is the largest possible size of an independent set <i>I</i> in <i>G</i> where each vertex of <i>I</i> has degree at least <i>d</i> in <i>G</i>. Upper bounds for the <i>d</i>-independence number in planar graphs are well-known for <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(d=3,4,5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mn>3</mn> <mo>,</mo> <mn>4</mn> <mo>,</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>, and can in fact be matched with constructions that actually have minimum degree <i>d</i>. In this paper, we explore the same questions for 1-planar graphs, i.e., graphs that can be drawn in the plane with at most one crossing per edge. We give upper bounds for the <i>d</i>-independence number for all <i>d</i>. Then we give constructions that match the upper bound, and (for small <i>d</i>) also have minimum degree <i>d</i>.</p>

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

On the d-independence number in 1-planar graphs

  • 期刊论文

  • 发表日期：

    2025年11月12日

查看全文
  • Therese Biedl,
  • Prosenjit Bose,
  • Babak Miraftab

摘要

The d-independence number of a graph G is the largest possible size of an independent set I in G where each vertex of I has degree at least d in G. Upper bounds for the d-independence number in planar graphs are well-known for \(d=3,4,5\) d = 3 , 4 , 5 , and can in fact be matched with constructions that actually have minimum degree d. In this paper, we explore the same questions for 1-planar graphs, i.e., graphs that can be drawn in the plane with at most one crossing per edge. We give upper bounds for the d-independence number for all d. Then we give constructions that match the upper bound, and (for small d) also have minimum degree d.