<p>The <i>d</i>-distance <i>p</i>-packing domination number <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\gamma _d^p(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a graph <i>G</i> is the cardinality of a smallest set of vertices of <i>G</i> which is both a <i>d</i>-distance dominating set and a <i>p</i>-packing. If no such set exists, then we set <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\gamma _d^p(G) = \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>. For an arbitrary strong product <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({G\boxtimes H}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>⊠</mo> <mi>H</mi> </mrow> </math></EquationSource> </InlineEquation> it is proved that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({\gamma _{d}^p(G\boxtimes H) \le \gamma _d^p(G) \gamma _d^p(H)}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mrow> <mi>d</mi> </mrow> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>⊠</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. By proving that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\gamma _{d}^{p}(P_m \boxtimes P_n) = \Big \lceil \frac{m}{2d+1} \Big \rceil \Big \lceil \frac{n}{2d+1} \Big \rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mrow> <mi>d</mi> </mrow> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>m</mi> </msub> <mo>⊠</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌈</mo> </mrow> <mfrac> <mi>m</mi> <mrow> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌉</mo> </mrow> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌈</mo> </mrow> <mfrac> <mi>n</mi> <mrow> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and that if <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\gamma _{d}^{p}(C_n) &lt; \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mrow> <mi>d</mi> </mrow> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\gamma _{d}^{p}(P_m \boxtimes C_n) = \Big \lceil \frac{m}{2d+1} \Big \rceil \Big \lceil \frac{n}{2d+1} \Big \rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mrow> <mi>d</mi> </mrow> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>m</mi> </msub> <mo>⊠</mo> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌈</mo> </mrow> <mfrac> <mi>m</mi> <mrow> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌉</mo> </mrow> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌈</mo> </mrow> <mfrac> <mi>n</mi> <mrow> <mn>2</mn> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the sharpness of the upper bound is demonstrated. On the other hand, infinite families of strong toruses are presented for which the strict inequality holds. For instance, we present strong toruses with difference 2 and demonstrate that the difference can be arbitrarily large if only one factor is a cycle. It is also conjectured that if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\gamma _d^p(G) = \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\gamma _d^p(G\boxtimes H) = \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>⊠</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation> for every graph <i>H</i>. Several results are proved which support the conjecture, in particular, if <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\gamma _d^p(C_m)= \infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mi>m</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\gamma _d^p(C_m \boxtimes C_n)=\infty \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>γ</mi> <mi>d</mi> <mi>p</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mi>m</mi> </msub> <mo>⊠</mo> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>∞</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

On d-Distance p-Packing Domination Number in Strong Products

  • Csilla Bujtás,
  • Vesna Iršič Chenoweth,
  • Sandi Klavžar,
  • Gang Zhang

摘要

The d-distance p-packing domination number \(\gamma _d^p(G)\) γ d p ( G ) of a graph G is the cardinality of a smallest set of vertices of G which is both a d-distance dominating set and a p-packing. If no such set exists, then we set \(\gamma _d^p(G) = \infty \) γ d p ( G ) = . For an arbitrary strong product \({G\boxtimes H}\) G H it is proved that \({\gamma _{d}^p(G\boxtimes H) \le \gamma _d^p(G) \gamma _d^p(H)}\) γ d p ( G H ) γ d p ( G ) γ d p ( H ) . By proving that \(\gamma _{d}^{p}(P_m \boxtimes P_n) = \Big \lceil \frac{m}{2d+1} \Big \rceil \Big \lceil \frac{n}{2d+1} \Big \rceil \) γ d p ( P m P n ) = m 2 d + 1 n 2 d + 1 , and that if \(\gamma _{d}^{p}(C_n) < \infty \) γ d p ( C n ) < , then \(\gamma _{d}^{p}(P_m \boxtimes C_n) = \Big \lceil \frac{m}{2d+1} \Big \rceil \Big \lceil \frac{n}{2d+1} \Big \rceil \) γ d p ( P m C n ) = m 2 d + 1 n 2 d + 1 , the sharpness of the upper bound is demonstrated. On the other hand, infinite families of strong toruses are presented for which the strict inequality holds. For instance, we present strong toruses with difference 2 and demonstrate that the difference can be arbitrarily large if only one factor is a cycle. It is also conjectured that if \(\gamma _d^p(G) = \infty \) γ d p ( G ) = , then \(\gamma _d^p(G\boxtimes H) = \infty \) γ d p ( G H ) = for every graph H. Several results are proved which support the conjecture, in particular, if \(\gamma _d^p(C_m)= \infty \) γ d p ( C m ) = , then \(\gamma _d^p(C_m \boxtimes C_n)=\infty \) γ d p ( C m C n ) = .