Some results on the maximum length of circuits of spread k in the d-cube (Q5556887)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3272064
Language Label Description Also known as
default for all languages
No label defined
    English
    Some results on the maximum length of circuits of spread k in the d-cube
    scientific article; zbMATH DE number 3272064

      Statements

      Some results on the maximum length of circuits of spread k in the d-cube (English)
      0 references
      1969
      0 references
      circuit codes
      0 references
      A circuit code of dimension \(d\) and spread \(k\ge 1\) is a simple circuit \(C\) in the graph \(I^d\) of the unit \(d\)-dimensional cube which satisfies the condition \(d(x,y)\ge \min(d_0(x,y),k)\) for all \(x\) and \(y\) in \(C\), where \(d(x,y)\) \([d_0(x,y)]\) is the graph-theoretic distance between \(x\) and \(y\) in \(I^d\) [in \(C\)]. Such circuits are useful as error-limiting codes. The longer the circuit, the greater is the accuracy; the greater the spread, the greater is the error-limiting capability. The author discusses the pairs \((d,k)\) for which \(K(d,k)\), the length of a longest \(d\)-circuit of spread \(k\), is known. \textit{R. C. Singleton} [Generalized snake-in-the-box codes, IEEE Trans. Electron. Comput. 15, No. 4, 596--602 (1966; \url{doi:10.1109/PGEC.1966.264382})] has shown that (1) \(K(d,k) = 2d\) if \(d< [3k/2] + 2\), stated without proof that (2) \(K([3k/2] +2,k) = 4k +4\) for \(k\) odd, and conjectured that (3) \(K([3k/2] +2,k) = 4k + 6\) for \(k\) even. The author proves (2) and (3), showing in the case of (2) that, up to an isomorphism of \(I^d\) there is only one \(d\)-circuit of spread \(k\) and length \(K(d,k)\) for \(d= [3k/2] +2\) and \(k\) odd. The author also shows that \(K([3k/2] +3,k) = 4k + 8\) for odd \(k\ge 9\).
      0 references

      Identifiers