Scholarlink

<p>For an arbitrary finite family of graphs, the distance labeling problem asks to assign labels to all nodes of every graph in the family in a way that allows one to recover the distance between any two nodes of any graph from their labels. The main goal is to minimize the number of unique labels used. We study this problem for the families <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {C}_n\)</EquationSource> </InlineEquation> consisting of cycles of all lengths between 3 and <i>n</i>. We observe that the exact solution for directed cycles is straightforward and focus on the undirected case. We design a labeling scheme requiring <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\frac{n\sqrt{n}}{\sqrt{6}}+O(n)\)</EquationSource> </InlineEquation> labels, which is almost twice less than is required by the earlier known scheme. Using the computer search, we find an optimal labeling for each <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(n\le 17\)</EquationSource> </InlineEquation>, showing that our scheme gives the results that are very close to the optimum.</p>

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

Distance labeling for families of cycles

  • 期刊论文

  • 发表日期：

    2026年1月31日

查看全文
  • Arseny M. Shur,
  • Mikhail Rubinchik

摘要

For an arbitrary finite family of graphs, the distance labeling problem asks to assign labels to all nodes of every graph in the family in a way that allows one to recover the distance between any two nodes of any graph from their labels. The main goal is to minimize the number of unique labels used. We study this problem for the families \(\mathcal {C}_n\) consisting of cycles of all lengths between 3 and n. We observe that the exact solution for directed cycles is straightforward and focus on the undirected case. We design a labeling scheme requiring \(\frac{n\sqrt{n}}{\sqrt{6}}+O(n)\) labels, which is almost twice less than is required by the earlier known scheme. Using the computer search, we find an optimal labeling for each \(n\le 17\) , showing that our scheme gives the results that are very close to the optimum.