Encoding Paths with Binary Arrays in a King’s Graph for Error-Free Data Transmission

<jats:title>Abstract</jats:title> <jats:p>In this study, we have chosen the computer network with the shape of a king’s graph. The king’s graph <jats:italic>G</jats:italic> is defined as a set of edges, that is <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$E=\{((i,j),(p,q))|i,p \in [0,M], j,q \in [0,N], M,N \in \textbf{Z},((i,j),(p,q))~{is\, an\, edge}\,\iff i = p \quad {and} \quad j = q\pm 1 \quad {or} \quad i = p\pm 1 \quad {and} \quad j = q \quad {or} \quad i = p\pm 1 \quad {and} \quad j = q\pm 1\}$$</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>E</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mo>(</mml:mo> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo>)</mml:mo> <mml:mo>,</mml:mo> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mo>|</mml:mo> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>M</mml:mi> <mml:mo>]</mml:mo> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo>]</mml:mo> <mml:mo>,</mml:mo> <mml:mi>M</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>Z</mml:mi> <mml:mo>,</mml:mo> <mml:mo>(</mml:mo> <mml:mo>(</mml:mo> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo>)</mml:mo> <mml:mo>,</mml:mo> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> <mml:mspace/> <mml:mrow> <mml:mi>i</mml:mi> <mml:mi>s</mml:mi> <mml:mspace/> <mml:mi>a</mml:mi> <mml:mi>n</mml:mi> <mml:mspace/> <mml:mi>e</mml:mi> <mml:mi>d</mml:mi> <mml:mi>g</mml:mi> <mml:mi>e</mml:mi> </mml:mrow> <mml:mspace/> <mml:mo>⟺</mml:mo> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mspace/> <mml:mrow> <mml:mi>and</mml:mi> </mml:mrow> <mml:mspace/> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mi>q</mml:mi> <mml:mo>±</mml:mo> <mml:mn>1</mml:mn> <mml:mspace/> <mml:mrow> <mml:mi>or</mml:mi> </mml:mrow> <mml:mspace/> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mo>±</mml:mo> <mml:mn>1</mml:mn> <mml:mspace/> <mml:mrow> <mml:mi>and</mml:mi> </mml:mrow> <mml:mspace/> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mi>q</mml:mi> <mml:mspace/> <mml:mrow> <mml:mi>or</mml:mi> </mml:mrow> <mml:mspace/> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mo>±</mml:mo> <mml:mn>1</mml:mn> <mml:mspace/> <mml:mrow> <mml:mi>and</mml:mi> </mml:mrow> <mml:mspace/> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mi>q</mml:mi> <mml:mo>±</mml:mo> <mml:mn>1</mml:mn> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> </jats:alternatives> </jats:inline-formula>. We also set a delivery rule, in which the shortest paths in the graph are used for the message deliveries, to restrict the source consumption. Then, the paths are encoded in a way that we discover using binary arrays based on other well-known encoding methods. We prove that the path-coding method we present prevents errors denoted by false positives from the graph. Data transfer issues from computer science served as the motivation for this study.</jats:p>