Fault Tolerance of Metric Basis Can Be Expensive

<jats:p>A set of vertices <jats:italic>S</jats:italic> is a resolving set of a graph <jats:italic>G</jats:italic>,  if for every pair of vertices <jats:italic>x</jats:italic> and <jats:italic>y</jats:italic> in <jats:italic>G</jats:italic>, there exists a vertex <jats:italic>s</jats:italic> in <jats:italic>S</jats:italic> such that <jats:italic>x</jats:italic> and <jats:italic>y</jats:italic> differ in distance to <jats:italic>s</jats:italic>. A smallest resolving set of <jats:italic>G</jats:italic> is called a metric basis. The metric dimension <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim}(G)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>dim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> is the cardinality of a metric basis of <jats:italic>G</jats:italic>. The notion of a metric basis is applied to the problem of placing sensors in a network, where the problem of sensor faults can arise. The fault-tolerant metric dimension <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{ftdim}(G)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>ftdim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> is the cardinality of a smallest resolving set <jats:italic>S</jats:italic> such that <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$S\setminus \{s\}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>\</mml:mo> <mml:mo>{</mml:mo> <mml:mi>s</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> remains a resolving set of <jats:italic>G</jats:italic> for every <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$s\in S$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula>. A natural question is how much more sensors need to be used to achieve a fault-tolerant metric basis. It is known in literature that there exists an upper bound on <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{ftdim}(G)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>ftdim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> which is exponential in terms of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim}(G),$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>dim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> i.e. <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{ftdim}(G)\le \textrm{dim}(G)(1+2\cdot 5^{\textrm{dim}(G)-1}).$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>ftdim</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mtext>dim</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:msup> <mml:mn>5</mml:mn> <mml:mrow> <mml:mtext>dim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> In this paper, we construct graphs <jats:italic>G</jats:italic> with <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{ftdim}(G)=\textrm{dim}(G)+2^{\textrm{dim}(G)-1}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>ftdim</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mtext>dim</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mtext>dim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> for any value of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim}(G)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>dim</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula>, so the exponential upper bound is necessary. We also extend these results to the <jats:italic>k</jats:italic>-metric dimension which is a generalization of the fault-tolerant metric dimension. First, we establish a similar exponential upper bound on <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim}_{k+1}(G)$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mtext>dim</mml:mtext> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> in terms of <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim}_{k}(G),$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mtext>dim</mml:mtext> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula> and then we show that there exists a graph for which <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\textrm{dim