Scholarlink

Abstract <p>Subset <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(V{\kern 1pt} ' \subset V(G)\)</EquationSource> <!--AutCont2570041Iordanskii-m1--> </InlineEquation> is called a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <!--AutCont2570041Iordanskii-m2--> </InlineEquation>-dominating set of vertices of graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(G\)</EquationSource> <!--AutCont2570041Iordanskii-m3--> </InlineEquation> with neighborhood <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <!--AutCont2570041Iordanskii-m4--> </InlineEquation> if for any vertex <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(v \in V\backslash V{\kern 1pt} '\)</EquationSource> <!--AutCont2570041Iordanskii-m5--> </InlineEquation> there is vertex <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(u \in V{\kern 1pt} '\)</EquationSource> <!--AutCont2570041Iordanskii-m6--> </InlineEquation> such that the length of the shortest path connecting these vertices <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(~d\left( {u,v{\;}} \right)~\,\, \leqslant \,\,\varepsilon \)</EquationSource> <!--AutCont2570041Iordanskii-m7--> </InlineEquation>; <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\({{\delta }_{\varepsilon }}(G)\)</EquationSource> <!--AutCont2570041Iordanskii-m8--> </InlineEquation> is the number of vertices in the minimal <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <!--AutCont2570041Iordanskii-m9--> </InlineEquation>-dominating set; <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\({{\delta }_{\varepsilon }}(G) = 1\)</EquationSource> <!--AutCont2570041Iordanskii-m10--> </InlineEquation> for <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(~r\left( G \right)~~~ \leqslant \varepsilon \leqslant d\left( G \right)\)</EquationSource> <!--AutCont2570041Iordanskii-m11--> </InlineEquation>; for <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\varepsilon &lt; r(G)\)</EquationSource> <!--AutCont2570041Iordanskii-m12--> </InlineEquation> the numbers <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\({{\delta }_{\varepsilon }}(G) &gt; 1\)</EquationSource> <!--AutCont2570041Iordanskii-m13--> </InlineEquation>, but the calculation of <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\({{\delta }_{1}}(G) = \delta (G)\)</EquationSource> <!--AutCont2570041Iordanskii-m14--> </InlineEquation> is an NP‑complete problem. This paper considers class of trees <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(t_{d}^{\rho }\)</EquationSource> <!--AutCont2570041Iordanskii-m15--> </InlineEquation> of diameter <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(d\)</EquationSource> <!--AutCont2570041Iordanskii-m16--> </InlineEquation> whose degrees of all internal vertices are equal to <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\rho \)</EquationSource> <!--AutCont2570041Iordanskii-m17--> </InlineEquation>. Constructive descriptions of trees <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(t \in t_{d}^{\rho }\)</EquationSource> <!--AutCont2570041Iordanskii-m18--> </InlineEquation> are given. Procedures are developed for computing the values of <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\({{\delta }_{\varepsilon }}(t)\)</EquationSource> <!--AutCont2570041Iordanskii-m19--> </InlineEquation> in the range <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(~~1 \leqslant \varepsilon &lt; r\left( t \right)\)</EquationSource> <!--AutCont2570041Iordanskii-m20--> </InlineEquation>. Asymptotic estimates are established for <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\({{\delta }_{\varepsilon }}(t)\)</EquationSource> <!--AutCont2570041Iordanskii-m21--> </InlineEquation> and their proportion of the total number of vertices in <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(t \in t_{d}^{\rho }\)</EquationSource> <!--AutCont2570041Iordanskii-m22--> </InlineEquation> as <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(d \to \infty \)</EquationSource> <!--AutCont2570041Iordanskii-m23--> </InlineEquation>. Computational examples are given.</p>

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

Dominating Sets with Neighborhoods for Trees

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • M. A. Iordanski

摘要

Abstract

Subset \(V{\kern 1pt} ' \subset V(G)\) is called a \(\varepsilon \) -dominating set of vertices of graph \(G\) with neighborhood \(\varepsilon \) if for any vertex \(v \in V\backslash V{\kern 1pt} '\) there is vertex \(u \in V{\kern 1pt} '\) such that the length of the shortest path connecting these vertices \(~d\left( {u,v{\;}} \right)~\,\, \leqslant \,\,\varepsilon \) ; \({{\delta }_{\varepsilon }}(G)\) is the number of vertices in the minimal \(\varepsilon \) -dominating set; \({{\delta }_{\varepsilon }}(G) = 1\) for \(~r\left( G \right)~~~ \leqslant \varepsilon \leqslant d\left( G \right)\) ; for \(\varepsilon < r(G)\) the numbers \({{\delta }_{\varepsilon }}(G) > 1\) , but the calculation of \({{\delta }_{1}}(G) = \delta (G)\) is an NP‑complete problem. This paper considers class of trees \(t_{d}^{\rho }\) of diameter \(d\) whose degrees of all internal vertices are equal to \(\rho \) . Constructive descriptions of trees \(t \in t_{d}^{\rho }\) are given. Procedures are developed for computing the values of \({{\delta }_{\varepsilon }}(t)\) in the range \(~~1 \leqslant \varepsilon < r\left( t \right)\) . Asymptotic estimates are established for \({{\delta }_{\varepsilon }}(t)\) and their proportion of the total number of vertices in \(t \in t_{d}^{\rho }\) as \(d \to \infty \) . Computational examples are given.