Scholarlink

<p>A subset <i>X</i> of vertices in a graph <i>G</i> is a <i>diameter 2 subset</i> if the distance of any two vertices of <i>X</i> is at most two <i>in G[X]</i>. Relaxing this notion, a subset <i>X</i> of vertices in a graph <i>G</i> is a <i>2-reachable subset</i> if the distance of any two vertices of <i>X</i> is at most two <i>in G</i>. Related to recent attempts to strengthen a well-known conjecture of Ryser, English et al. conjectured that the vertices of a 2-edge-colored cocktail party graph (the graph obtained from a complete graph with an even number of vertices by deleting a perfect matching) can be covered by the vertices of two monochromatic diameter 2 subsets. In this note we prove the relaxed form of this conjecture, replacing diameter 2 by 2-reachable. An immediate corollary is that 2-colored cocktail party graphs on <i>n</i> vertices must contain a monochromatic 2-reachable subset with at least <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n\over 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation> vertices (and this is best possible).</p>

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

2-Reachable Subsets in Two-Colored Graphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月25日

查看全文
  • András Gyárfás,
  • Gábor N. Sárközy

摘要

A subset X of vertices in a graph G is a diameter 2 subset if the distance of any two vertices of X is at most two in G[X]. Relaxing this notion, a subset X of vertices in a graph G is a 2-reachable subset if the distance of any two vertices of X is at most two in G. Related to recent attempts to strengthen a well-known conjecture of Ryser, English et al. conjectured that the vertices of a 2-edge-colored cocktail party graph (the graph obtained from a complete graph with an even number of vertices by deleting a perfect matching) can be covered by the vertices of two monochromatic diameter 2 subsets. In this note we prove the relaxed form of this conjecture, replacing diameter 2 by 2-reachable. An immediate corollary is that 2-colored cocktail party graphs on n vertices must contain a monochromatic 2-reachable subset with at least \(n\over 2\) n 2 vertices (and this is best possible).