<p>It is known that, for any positive integer <i>n</i>,&#xa0; the path <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(P_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> of order <i>n</i> satisfies the Vizing’s conjecture, that is, for any graph <i>G</i>,&#xa0; <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\gamma (G\square P_n)\ge \gamma (G)\gamma (P_n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\gamma \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation> stands for the domination number and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\square \)</EquationSource> <EquationSource Format="MATHML"><math> <mo>□</mo> </math></EquationSource> </InlineEquation> for the Cartesian product. In an attempt to prove Vizing’s conjecture, Clark and Suen proved in 2000 that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\gamma (X\square Y)\ge \frac{1}{2}\gamma (X)\gamma (Y)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo>□</mo> <mi>Y</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>Y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any pair of graphs <i>X</i> and <i>Y</i>. Combining these two inequalities, we have <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\gamma (X\square Y\square P_n)\ge \frac{1}{2}\gamma (X)\gamma (Y)\gamma (P_n).\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo>□</mo> <mi>Y</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>Y</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> In this paper, we use space projections to build a general framework to obtain a lower bound for the domination number of a triple Cartesian product of graphs. As an application, we show that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\gamma (X\square Y\square P_{n})\ge c_n\gamma (X)\gamma (Y)\gamma (P_{n}),\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo>□</mo> <mi>Y</mi> <mo>□</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msub> <mi>c</mi> <mi>n</mi> </msub> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <mi>Y</mi> <mo stretchy="false">)</mo> </mrow> <mi>γ</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> where <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(c_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>c</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is almost <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\frac{3}{4}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>3</mn> <mn>4</mn> </mfrac> </math></EquationSource> </InlineEquation> when <i>n</i> is big enough.</p>

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

A Lower Bound for the Domination Number of Triple Cartesian Products of Graphs

  • Omar Tout

摘要

It is known that, for any positive integer n,  the path \(P_n\) P n of order n satisfies the Vizing’s conjecture, that is, for any graph G \(\gamma (G\square P_n)\ge \gamma (G)\gamma (P_n)\) γ ( G P n ) γ ( G ) γ ( P n ) where \(\gamma \) γ stands for the domination number and \(\square \) for the Cartesian product. In an attempt to prove Vizing’s conjecture, Clark and Suen proved in 2000 that \(\gamma (X\square Y)\ge \frac{1}{2}\gamma (X)\gamma (Y)\) γ ( X Y ) 1 2 γ ( X ) γ ( Y ) for any pair of graphs X and Y. Combining these two inequalities, we have \(\gamma (X\square Y\square P_n)\ge \frac{1}{2}\gamma (X)\gamma (Y)\gamma (P_n).\) γ ( X Y P n ) 1 2 γ ( X ) γ ( Y ) γ ( P n ) . In this paper, we use space projections to build a general framework to obtain a lower bound for the domination number of a triple Cartesian product of graphs. As an application, we show that \(\gamma (X\square Y\square P_{n})\ge c_n\gamma (X)\gamma (Y)\gamma (P_{n}),\) γ ( X Y P n ) c n γ ( X ) γ ( Y ) γ ( P n ) , where \(c_n\) c n is almost \(\frac{3}{4}\) 3 4 when n is big enough.